אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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−ε 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 ε.

The construction is based on algebraic-geometric (AG) codes. Our main observation is that the output list of AG codes with subfield evaluation points is contained in an affine shift of the image of a block-triangular-Toeplitz (BTT) matrix, and that the list size can be reduced to a constant by restricting the message space to a BTT evasive subspace.

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

More details.

Lecture Video.