Thursday, October 30, 2003
B17 Upson Hall
Dr. Madhu Sudan
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.