Linear-algebraic List Decoding and Subspace-evasive Sets


Venkatesan Guruswami


Carnegie Mellon University
Computer Science Department
Gates-Hillman Complex 7211
5000 Forbes Avenue
Pittsburgh, PA 15213
United States of America


Tuesday, 31 July 2012, 16:00 to 17:00



We will describe a simple linear-algebraic approach to list decode Reed-Solomon codes with evaluation points from a subfield. The algorithm is able to correct an error fraction approaching the information-theoretically maximum limit of $1-R$ where $R$ is the rate of the code.

The algorithm can be thought of as a higher-dimensional version of the Welch-Berlekamp decoder, and pins down the candidate solutions to a subspace of non-trivially smaller dimension. By pre-coding the messages to belong to a pseudorandomly constructed "subspace-evasive set" that has small intersection with subspaces of the sort output by the decoder, one can prune the subspace to a small list of close-by codewords in polynomial time.

This approach to list decoding is quite versatile, and applies to variants of Reed-Solomon codes (the context where it was first discovered), folded algebraic-geometric codes (which yields efficiently list-decodable codes with simultaneously near-optimal rate, list size, and alphabet size), and Gabidulin codes (the rank-metric analog of Reed-Solomon codes). Time permitting, we might briefly touch upon some of these variants.

Based on joint work with Chaoping Xing.