[PRL] Mahdu Sudan, Wed 10/13, 1100am, 366 WVH

[Mitchell Wand]

Ravi says:

Next Wed, 10/13, at 11 in 366 WVH, Madhu Sudan will be giving a colloquium
on coding theory. It is not often that we get an opportunity to listen to a
speaker of his stature. Please try to make it, please also encourage your
students to attend.

Mitch adds:

This guy is famous (check out his prizes below!).  

--Mitch 

================================================================

Title: List Decoding of Error-correcting Codes

Time/Location: 11am, 10/13, 366 WVH

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 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.

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).