一、题目

Efficient List-Decoding with Constant Alphabet and List Sizes

二、主讲人

郭泽宇（海法大学）

三、时间

2020年12月24日 下午14：00-15：00

四、地点

华岗苑东楼119报告厅

五、摘要

The notion of list-decoding, introduced by Elias in the 1950s, is a natural generalization of unique decoding, where the decoder is allowed to output a list of codewords that contains the transmitted codeword instead of a single codeword. Besides being a fundamental concept in coding theory, list decoding has found diverse applications in theoretical computer science.

Error-correcting codes of rate $R$ that are list-decodable up to the relative radius $1 - R - \epsilon$ are said to achieve the list-decoding capacity. The first explicit capacity-achieving list-decodable codes, known as folded Reed-Solomon (FRS) codes, were constructed by Guruswami and Rudra in their celebrated paper [Guruswami and Rudra, 2005]. A disadvantage of FRS codes, however, is that the alphabet size is not constant and has to grow with the block length of the codes.

In this talk, I will present our recent explicit and efficient algebraic construction of capacity-achieving list-decodable codes whose list size and alphabet size are both constant, depending only on the gap to capacity $\epsilon$.

This is joint work with Noga Ron-Zewi. No prior knowledge of algebraic-geometric codes is assumed.

六、报告人简介

郭泽宇，2017年在加州理工学院获计算机科学博士学位，现任以色列海法大学博士后。研究方向为理论计算机科学，研究兴趣包括伪随机理论，编码理论，计算复杂性理论，以及代数方法在理论计算机科学中的应用。