Venkatesan Guruswami: List Decoding by Evading Subspaces.

A natural "folded" variant of the classical Reed-Solomon codes are known to be list-decodable with optimal redundancy (in particular, only epsilon higher than the worst-case error fraction, for any desired epsilon > 0). The last couple of years have seen improvements of this result that reduce the alphabet and list sizes to a constant depending only on epsilon.

The new developments are based on a combination of two ingredients: (i) a simple yet versatile linear-algebraic approach to list error-correction that first pins down the candidate solutions to a low-dimensional or well-structured subspace, and (ii) pre-coding the messages to belong to appropriate subspace-evasive sets or subspace designs that have small intersection with any subspace that could be output by the linear-algebraic list decoder.

In this talk, I'll survey some of these results. For the technical part, I will present the linear-algebraic algorithm to list decode folded Reed-Solomon codes, and hope to illustrate the ideas behind more advanced extensions (to variants of algebraic-geometric codes) by describing the linear-algebraic algorithm and its combination with subspace designs in the context of Reed-Solomon codes with evaluation points belonging to a subfield.

The talk should be self-contained. Partly based on joint works with Chaoping Xing (STOC'12, '13) and Carol Wang (IEEE Trans. Info. Theory 59(6): 2013)