The PCP Theorem by Gap Amplification
| COMPUTER SCIENCE/DISCRETE MATH, I | |
| Topic: | The PCP Theorem by Gap Amplification |
| Speaker: | Irit Dinur |
| Affiliation: | Hebrew University of Jerusalem |
| Date: | Monday, June 13 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
Given a set of variables, and a set of local constraints over them (e.g. a 3CNF formula) define the "satisfiability-gap" of the system as the smallest fraction of unsatisfiable constraints.
We will describe a new proof for the PCP theorem of [AS,ALMSS] based on an iterative gap amplification step. This step is a linear-time transformation that doubles the satisfiability gap of a given system.
The transformation is based on applying "graph powering" to a system of constraints. It is proven via random-walk arguments, relying on the edge expansion of the underlying graph structure.
The main result can also be applied towards constructing *short* PCPs and locally-testable codes whose length is linear up to a polylog factor, and whose correctness can be probabilistically verified by making a constant number of queries. This answers an open question of Ben-Sasson et al. (STOC '04).