Probabilistically Checkable Proofs and Applications

Probabilistically Checkable Proofs (PCPs) are proof systems that allow a verifier to check the correctness of a proof by reading only a few locations — sometimes as few as two. Since their introduction in the 1990s, PCPs have become a central tool in theoretical computer science, with applications to areas such as hardness of approximation, coding theory, and cryptography.

 

In this talk, I will present several new developments in PCPs, including the first PCPs achieving nearly optimal alphabet–soundness tradeoff, yielding new hardness-of-approximation results, as well as the first 3-query low-soundness PCPs of proximity, which resolve a conjecture about local decoding from 2005.