EECS Joint Colloquium Distinguished Lecture Series

Wednesday, October 6, 2004
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Professor Madhu Sudan

Electrical Engineering and Computer Science Department
Massachusetts Institute of Technology


List Decoding of Error-Correcting Codes




The task of dealing with errors (or correcting them) lies at the very heart of communication and computation. The mathematical foundations for this task were laid in two concurrent and interdependent works by Shannon and Hamming in the late 1940s. The two theories are strikingly powerful and distinct in their modelling of the error. Shannon's theory models errors as effected by some probabilistic/stochastic process, while Hamming envisions them as being introduced by an adversary. While the two theories share a lot in the underlying tools, the quantitative results are sharply diverging. Shannon's theory shows that a channel that corrupts (arbitrarily) close to 50% of the transmitted bits can still be used for transmission of information. Hamming's theory in contrast has often been interpreted to suggest it can handle at most 25% error on a binary channel.

So what can we do if an adversary is given the power to introduce more than 25% errors? Can we protect information against this, or do we just have to give up? The notion of list-decoding addresses precisely this question, and shows that under a relaxed notion of "decoding" (or recovering from errors), the quantitative gaps between the Shannon and Hamming theories can be bridged. In this talk, we will describe this notion and some recent algorithmic developments.

Based on joint work with V. Guruswami (MIT & U. Washington).


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 a Professor of Computer Science and Engineering 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. He was a Fellow at the Radcliffe Institute for Advanced Study from 2003-2004.

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, and was the program committee chair of the IEEE Conference on Computational Complexity '01, and the IEEE Symposium on Foundations of Computer Science '03. He is a member of the editorial boards of the Journal of the ACM, SIAM Journal on Computing, and Information and Computation, and a member of the scientific board of the Electronic Colloquium on Computational Complexity (ECCC). Madhu Sudan is a recipient of numerous awards including the ACM Doctoral Dissertation Award (1992), the IEEE Information Theory Society Paper Award (2000), the Godel Prize (2001), the Nevanlinna Prize (2002) and Distinguished Alumni Awards from the Indian Institute of Technology at Delhi (2004) and the CS division of the University of California at Berkeley (2003).