[Colloq] Reminder **Talk, TODAY, 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.



_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq