ABSTRACT


Errorcorrecting 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 errorcorrecting 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 errorcorrecting 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 illposed. However, it turns out that there is a reasonable notion of recovery called ``listdecoding'' 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 listdecoding algorithms for one of the most popular family of errorcorrecting codes  the ReedSolomon codes. Joint work with Venkatesan Guruswami (MIT > UCB > U.Wash.) About the speakerMadhu 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 listdecoding algorithms for errorcorrecting 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). Return to Applied Math Colloquium home page 