Computer Science/Discrete Mathematics Seminar II

In the theory of error-correcting codes, list decoding allows a decoder to output a list of candidates when attempting to remove noise from a corrupted input. The constructions and algorithms for such list decodable codes has had numerous applications in pseudorandomness and complexity theory.

In this talk, we will focus on the classical constructions of optimally list decodable codes, first achieved by Guruswami and Rudra. These constructions are based on bounded degree polynomials over finite fields, and are called Folded Reed—Solomon Codes. In the 20 years since their introduction, we have had significant improvement in our understanding of these codes, and we will focus on the significant structural and algorithmic breakthroughs in the last couple of years.

In the second half, we will see how a different class of codes based on expander graphs has recently been shown to enjoy many similar features to the algebraic codes above. Further, there are common features in the proofs of list decodability of the two classes of codes, hinting at a broader theory.

Based on joint work with Vikrant Ashvinkumar, Mursalin Habib, Fernando Granha Jeronimo, Tushant Mittal and Madhur Tulsiani.