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.

Loading more stuff…

Hmm…it looks like things are taking a while to load. Try again?

Loading videos…