Abstract
List-decodable codes are important in theory and practice. List-decoding is a relaxation of unique decoding, where we only need to recover the codeword up to a small list. This allows the codes to tolerate approximately twice as much error, giving them applications such as group testing and compressed sensing. List-decodable codes also have a fundamental mathematical definition, giving them “extraneous” applications that have no obvious need for error correction, such as in pseudorandomness, computational complexity, and cryptography.
A fundamental question is: what kinds of codes are optimally list-decodable? Uniformly random codes, where each codeword is sampled independently at random, achieve the best-known parameters in list-decoding. I will discuss recent progress on whether much more structured random ensembles of codes — such as random linear codes and randomly punctured Reed-Solomon codes — enjoy list-decoding properties comparable to those of uniformly random codes.