Linear-algebraic List Decoding and Subspace-evasive Sets

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.