Local Decoding of Polynomials and its Application
Chris Umans, California Institute of Technology
Error-correcting codes lie at the heart of a number of powerful results in Computer Science. Among the most useful error-correcting codes are codes based on polynomials, and they derive their error-correcting properties from the fact that polynomials of low degree cannot have many roots.
Certain polynomial-based codes have an amazing additional property: any given symbol of the original encoded information string can be retrieved from a corrupted codeword by examining only a tiny fraction of the overall object. This is called "local decoding." The existence of locally decodable codes is crucial to a number of the most striking uses of algebra in computer science (especially theoretical computer science). I will sketch how locally decodable codes are used in Probabilistically Checkable Proofs (mathematical proofs whose validity can be checked by randomly examining only a tiny portion of the proof), and the transformation of computationally hard problems into "even harder" problems, which are in turn useful in cryptography and elsewhere within Computational Complexity.