Speaker: Venkatesan Guraswami
Affiliation: MIT
Date: 3/13/01
Time and Location: 4:15 PM, B11 Kimball Hall

Error-correcting codes are combinatorial objects designed to achieve reliable transmission of information on a noisy channel. A fundamental algorithmic challenge in coding theory and practice is to efficiently decode the original transmitted message even when a few symbols of the received word are in error. The naive search algorithm runs in exponential time, and several classical polynomial time decoding algorithms are known for specific code families. Traditionally, however, these algorithms have been constrained to output a unique codeword. Thus they faced a "combinatorial barrier" and could only correct up to d/2 errors, where d is the minimum distance of the code.

An alternate notion of decoding called *list decoding*, proposed independently by Elias and Wozencraft in the late 50s, allows the decoder to output a list of *all* codewords that differ from the received word in a certain number of positions. It thus permits recovery from errors beyond the d/2 barrier. Though the notion of
list decoding is itself quite old, till recently no *efficient* algorithms were known for decoding beyond half the minimum distance. The last few years have witnessed the development of efficient list decoding algorithms to correct significantly more than d/2 errors for several families of error-correcting codes.

In this talk, I will motivate the notion of list decoding, and then discuss a list decoding algorithm for an important family of codes called Reed-Solomon codes. I will then briefly survey a few other main results in this area, including new constructions of good list-decodable codes, combinatorial results on the asymptotic performance of list decoding, and a sample of applications both within
and outside of coding theory. I will also outline some of the future challenges in this area, including that of achieving channel capacities under adversarial error models.

(This talk covers joint works with Johan Hastad, Piotr Indyk, Amit Sahai, Madhu Sudan and David Zuckerman.)