CS Colloquium
Thursday, October 30, 2003
4:15 PM
B17 Upson Hall

Dr. Madhu Sudan
MIT

List Decoding and Complexity Theory


The theory of error-correcting codes has long provided many useful concepts, tools and constructions to theoretical computer science. Over the course of the past fifteen years a new strain of applications, revolving around the notion of "list-decoding," have linked the two areas. In this talk, I'll describe the new notion and some of the connections, and give a biased opinion on why I think this link is here to stay.