Bridging Shannon and Hamming: List Error-Correction with Optimal Rate

Error-correcting codes tackle the fundamental problem of recovering from errors during data communication and storage. A basic issue in coding theory concerns the modeling of the channel noise. Shannon’s theory models the channel as a stochastic process with a known probability law. Hamming suggested a combinatorial approach where the channel causes worst-case errors subject only to a limit on the number of errors. These two approaches share a lot of common tools, however in terms of quantitative results, the classical results for worst-case errors were much weaker. We survey recent progress on list decoding, highlighting its power and generality as an avenue to construct codes resilient to worst-case errors with information rates similar to what is possible against probabilistic errors. In particular, we discuss recent explicit constructions of list-decodable codes with information-theoretically optimal redundancy that is arbitrarily close to the fraction of symbols that can be corrupted by worst-case errors.