Abstract: Error-correcting codes are combinatorial designs constructed to deal with the problem of noise in information transmission. A code describes how to judiciously add redundancy information so that if a small number of errors occur during transmission, then this can be detected. Furthermore if the number of errors that occur is even smaller, then one can even correct the errors in an information theoretic sense. In the seminal paper that introduced error-correcting codes, Hamming (1950) showed that a code is capable of detecting d errors if and only if it is capable of correcting d/2 errors uniquely. Subsequently the study of error-correcting codes has led to many codes where these tasks are achievable algorithmically.

What happens when if we try to recover from more than d/2 errors when the code is designed to detect d errors? Hamming's result is often misinterpreted to suggest that this task is ill-posed. However, it turns out that there is a reasonable notion of recovery called ``list-decoding'' dating back to Elias (1957), where the decoding algorithm simply outputs a list of codewords that are close to a received vector. In this talk we will discuss this notion and describe some recent works that give simple and efficient list-decoding algorithms for one of the most popular family of error-correcting codes --- the Reed-Solomon codes.

Joint work with Venkatesan Guruswami.

Mon Mar 18 10-12am: Survey of list-decoding algorithms. (Room 110, Maths Building) In this talk, second in the series, we will show how to extend the ``Reed-Solomon list-decoding'' algorithms to other algebraic/number-theoretic error-correcting codes; and show how to use it modularly to correct codes based on multivariate polynomials. Time permitting, we will also survey other list-decoding algorithms in the literature.

Wed Mar 20 10.30-12: Combinatorics of list-decoding. (Room 201, Ross Building) The classical parameters associated with an error-correcting code are its rate, and distance. List-decoding introduces a new (family of) parameter(s) called the list-decoding radius: Roughly, how many errors can be corrected when the output list is bounded in size. In this talk, third in the series, we will discuss the relationship of this parameter to the classical ones.