Robust PCPs of Proximity, Short PCPs, and Applications to Coding

Abstract

The PCP theorem [AS, ALMSS] specifies a way of encoding any mathematical proof such that the validity of the proof can be verified probabilistically by querying the proof only at a constant number of locations. Furthermore, this encoding is complete and sound, i.e., valid proofs of true statements are always accepted while invalid proofs are accepted with probability at most 1/2. A natural question that arises in the construction of PCPs is by how much does this encoding blow up the original proof while retaining the constant number of queries into the proof. We study the trade-off between the length of PCPs and their query complexity, and produce the shortest known PCPs (to date), of nearly linear size. In this talk, intended to a general audience, we'll describe some of the tools used to obtain these highly-efficient PCPs, and some of their applications.

Joint work with: Oded Goldreich (Weizmann & Radcliffe), Prahladh Harsha (MIT), Madhu Sudan (MIT & Radcliffe) and Salil Vadhan (Harvard & Radcliffe).