[Colloq] Talk, Wed. Oct. 13, 11am - Madhu Sudhan, MIT

[Rachel Kalweit]

College of Computer and Information Science Colloquium

presents
Madhu Sudan
MIT

who will speak on:
List Decoding of Error-correcting Codes


Wednesday, October 13, 2004
11:00am
366 West Village H
Northeastern University

ABSTRACT

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 a 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 corrupt (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 Venkatesan Guruswami (MIT & U.Wash.)
Bio
Madhu Sudan received his BTech  from  IIT Delhi (1987) and his  PhD from 
Berkeley (1992). He is a Professor of Computer Science and Engineering 
at MIT.  He is on the editorial boards of the JACM, 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) 
and the Nevanlinna Prize (2002). He is best known for his works on 
probabilistic checking of proofs, and on the design of list-decoding 
algorithms for  error-correcting codes.