List decoding of error-correcting codes

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 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 (MIT -> UCB -> U.Wash.)

About the speaker

		  
Madhu  Sudan  recieved  his  Bachelor's  degree  from  the Indian
Institute of Technology at New Delhi in 1987 and his  Ph.D.  from
the University of California at Berkeley in 1992.  Madhu Sudan is
an  Associate  Professor  in   the   Department   of   Electrical
Engineering  and  Computer Science at the Massachusetts Institute
of Technology.  He was a Research Staff Member at IBM's Thomas J.
Watson  Research Center in Yorktown Heights, NY from 1992 to 1997
and has been at his current position at MIT since 1997.

Madhu Sudan's research interests include computational complexity
theory,  algorithms  and coding theory.  He is best known for his
works on  probabilistic  checking  of  proofs, and on the  design
of   list-decoding   algorithms   for  error-correcting codes. He
has served on numerous program committees   for  conferences   in
theoretical    computer   science   including  STOC'95,  FOCS'97,
SODA'98, FOCS'01 and was the  program  committee  chair   of  the
IEEE Conference on Computational Complexity '01.  He is currently
a  member  of  the  editorial  boards  of  the  SIAM  Journal  on
Computing,   the   SIAM  Journal  on  Discrete  Mathematics,  and
Information and Computation.  Madhu Sudan is a recipient of ACM's
Doctoral   Dissertation   Award   (1993),  the  Alfred  P.  Sloan
Foundation Fellowship (1997), the NSF Career  Award  (1998),  the
IEEE  Information  Theory  Paper  Award  (2000), the Goedel Prize
(2001), and the Nevanlinna Prize (2002).