Abstract:

Given a set of variables, and a set of local constraints over them
(e.g. a 3CNF formula) define the "unsat-value" 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 unsat-value 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).