Coping with choices - List Decoding in Coding Theory

Title of the Talk: Coping with choices - List Decoding in Coding Theory
Speakers: Shashank Srivastava
Host Faculty: Dr.Rogers Mathew
Date: Dec 15, 2025

Abstract: The goal of error correcting codes is to encode data in a way that allows for this data to be recovered even if the encoded copy is corrupted by an adversary. The usual algorithmic challenge associated with codes, called decoding, is to output the uncorrupted copy of data by looking only at the corrupted copy. However, when noise levels are high, the same corrupted copy could correspond to multiple uncorrupted copies. The task of list decoding is to output all such candidates. In this talk, we will talk about what makes list decoding interesting and challenging, and its connections to other areas in CS. We will then survey recent progress in list decoding for codes based on algebra and on expander graphs.

Speaker Bio: Shashank Srivastava is a joint postdoc between Institute for Advanced Study (IAS), Princeton and DIMACS, Rutgers University. Before this, he obtained a PhD in 2024 from TTI Chicago and a BTech in 2018 from IIT Kharagpur. Shashank’s research focuses on coding theory and spectral algorithms, and his work has won Best Paper and Best Student Paper awards at SODA.