Property Testing of Codes - Results, Methods and Limitations
Speaker: Tali Kaufman , Massachusetts Institute of Technology
Date: May 8 2006
Time: 4:15PM to 5:15PM
Location: 32-G575 (Theory Lab)
Host: Ronitt Rubinfeld, Massachusetts Institute of Technology
Contact: Kevin Matulef, 3-5883, matulef@mit.edu
Relevant URL: http://theory.csail.mit.edu/toc-seminars/PLZ NOTE DAY CHANGE!
A code is a set of vectors with typically large pairwise (Hamming) distance. Testing of a code is the ability to perform a few queries into an input vector and decide if the vector at hand belongs to the code or it is far from every vector in the code. Such a decision should be correct with high probability. A code is said to be "locally testable" if it can be tested using a constant number of queries. The study of property testing in general, and testing of codes in particular, is nowadays a very active field in theoretical computer science.
In this talk I will discuss two common approaches for proving local testability of codes. The "self-correction approach" that was used for obtaining local testability of Generalized Reed-Muller codes and the "spectra approach" that was useful for proving local testability of almost orthogonal codes. I will also discuss the limitations of these approaches. Namely, they are not likely to be useful for proving local testability of a good code (if such a code exist).
No prior knowledge is assumed.
The talk is based on joint works with Noga Alon, Michael Krivelevich, Simon Litsyn and Dana Ron.
See other events that are part of Theory Colloquium Spring 2006
See other events happening in May 2006
