
List Decoding: Algebraic and Combinatorial
Shashank Srivastava, a researcher at the Institute for Advanced Study, gives this Computer Science/Discrete Mathematics seminar on list decoding, the technique in coding theory that lets a decoder return a short list of candidates rather than a single guess when correcting a noisy signal. He starts with the classical construction of optimally list decodable codes, first achieved by Guruswami and Rudra using bounded degree polynomials over finite fields, known as Folded Reed-Solomon Codes, and traces the structural and algorithmic progress made on them over the past two years. The second half turns to a different family of codes built from expander graphs, showing how they have recently been proven to share many of the same list decodability properties as the algebraic codes, with overlapping proof techniques suggesting a more general theory connecting the two. The talk draws on joint work with Vikrant Ashvinkumar, Mursalin Habib, Fernando Granha Jeronimo, Tushant Mittal, and Madhur Tulsiani, aimed at an audience already versed in coding theory and complexity.