Institute for Interdisciplinary Information Sciences (IIIS)

home>Events>Upcoming Events>Institute Seminars

Sparse High-Distance Linear Codes are Locally Testable and Correctable

Speaker: Madhu Sudan MIT
Time: 2008-10-10 17:00-2008-10-10 17:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

A general theme in recent research in property testing is the isolation of minimal features of a "property'' that can make it locally testable. We consider this goal in the context of linear error-correcting codes, and provide one such class of features. We show that if the code has very large distance (codeword of length n should differ in at least $1/2 - 1/n^epsilon$ fraction of coordinates) and few codewords (bounded by a polynomial in n), then the codes are locally testable. The testability of Hadamard codes (first shown by Blum-Luby-Rubinfeld) and dual-BCH codes (shown by Kaufman and Litsyn) can be seen as special cases of this result.

Our proof technique goes back to the work of Kaufman and Litsyn that revolve around the MacWilliams Identities and Krawtchouk polynomials. Part of the goal of the talk is to increase awareness of these concepts among the CS audience
and to explain how these can be viewed/manipulated to get Property Testing results.

Joint work with Tali Kaufman (MIT & IAS)

Short Bio:

Madhu Sudan received his Bachelor's degree from the Indian Institute of Technology at New Delhi in 1987 and his Ph.D. from the University of California at Berkeley in 1992. From 1992-1997 he was a Research Staff Member at IBM's Thomas J. Watson Research Center. In 1997, he moved to MIT where he is now the Fujitsu Professor of Electrical Engineering and Computer Science, and as Associate Director of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). He was a Fellow at the Radcliffe Institute for Advanced Study from 2003-2004, and a Guggenheim Fellow from 2005-2006.

Madhu Sudan's research interests include computational complexity theory, algorithms and coding theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. He has served on numerous program committees for conferences in theoretical computer science, and was the program committee chair of the IEEE Conference on Computational Complexity '01, and the IEEE Symposium on Foundations of Computer Science '03. He is the chief editor of Foundations and Trends in Theoretical Computer Science, a new journal publishing surveys in the field. He is currently a member of the editorial boards of the Journal of the ACM and the SIAM Journal on Computing. Previously he served on the boards of the SIAM Journal on Discrete Mathematics, Information and Computation, and the IEEE Transactions on Information Theory.

In 2002, Madhu Sudan was awarded the Nevanlinna Prize, for outstanding contributions to the Mathematics of computer science, at the International Congress of Mathematicians in Beijing. Madhu Sudan's other awards include the ACM Doctoral Dissertation Award (1992), the IEEE Information Theory Society Paper Award (2000) and the Godel Prize (2001),Distinguished Alumnus Award of the University of California at Berkeley (2003), and Distinguished Alumnus Award of the Indian Institute of Technology at Delhi (2004).