The PCP theorem by gap amplification

We present a new proof of the PCP theorem that is based on a combinatorial amplification lemma. The unsat value of a set of constraints C = (c 1 ,...,c n ), denoted UNSAT(C), is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the underlying variables.We describe a new combinatorial amplification transformation that doubles the unsat-value of a constraint-system, with only a linear blowup in the size of the system. The amplification step causes an increase in alphabet-size that is corrected by a PCP composition step. Iterative application of these two steps yields a proof for the PCP theorem.The amplification lemma relies on a new notion of "graph powering" that can be applied to systems of constraints. This powering amplifies the unsat-value of a constraint system provided that the underlying graph structure is an expander.We also apply the amplification lemma to construct 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. Namely, we prove SAT ∈ PCP 1/2,1 [log 2 (n • poly log n),O(1)].

Authors

• Irit Dinur

Keywords

• PCP
• gap amplification