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 somewhat surprising connections to other areas in CS. We will then survey recent progress in list decoding for codes based on algebra and on expander graphs.
Short Bio: Shashank Srivastava is a joint postdoc between Institute for Advanced Study (IAS) 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.
