Old and New PCP Constructions

The PCP theorem (AS,ALMSS 1991) guarantees that every NP language has a probabilistically checkable proof (PCP) system allowing a verifier to check a witness very efficiently using randomness, and allowing for small error.

Most of the talk will not assume prior knowledge, but I will also devote some time to some recent work joint with Dinur and Kindler.

In this work we make (some) progress towards proving the so-called "sliding-scale conjecture". This is a conjecture of Bellare-Goldreich-Lund-Russel from 1993 about the tradeoff between the number of bits read from the PCP proof and the error of the verifier. Our work revisits older constructions and analyzes them using the more modern "modular-composition" approach (based on joint work with Irit Dinur and Guy Kindler).