We describe 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 prove a new combinatorial amplification lemma that doubles the

unsat-value of a constraint-system, with only a linear blowup in the

size of the system. Iterative application of this lemma 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 \in

PCP_{\half,1}[\log_2(n\cdot\poly\log n),\,O(1)]$. This answers an

open question of Ben-Sasson et al. (STOC '04).

Let C={c_1,...,c_n} be a set of constraints over a set of

variables. The {\em satisfiability-gap} of C is the smallest

fraction of unsatisfied constraints, ranging over all possible

assignments for the variables.

We prove a new combinatorial amplification lemma that doubles the

satisfiability-gap of a constraint-system, with only a linear blowup

in the size of the system. Iterative application of this lemma

yields a self-contained (combinatorial) 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 satisfiability-gap 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 {\em quasi-linear}, and whose

correctness can be probabilistically verified by making a {\em

constant} number of queries. Namely, we prove SAT \in

PCP_{0.5,1}[log(n * polylog n) , O(1)]. This answers an

open question of Ben-Sasson et al. (STOC '04).

The gap amplification lemma of Dinur (ECCC TR05-46) states that

the satisfiability gap of every d-regular constraint expander graph G (with

self-loops) can be amplified by graph powering, as long as the

satisfiability gap of G is not too large. We show that the last requirement

is necessary. Namely, for infinitely many d and every t, there exists an

integer n and a d-regular constraint expander G on n vertices over alphabet

{0, 1} such that sat-gap(G) > 1/2 - o(d), but sat-gap(G^t) < 1/2.

Comment #2 Authors: Jaikumar Radhakrishnan

Accepted on: 4th November 2005 09:38

Downloads: 3650

Keywords:

This note is based on the original version of Irit Dinur's paper (ECCC

TR05-046). It contains two suggestions concerning the product

construction. First, instead of using paths of a fixed length t, one

can use paths with varying lengths in order to simplify some

calculations. Second, one can view Proposition 2.4 as guaranteeing

some sort of pairwise independence, and use the second-moment method

instead of explicitly bounding the overcount (as in Lemma 5.3).

Comment #3 Authors: Oded Goldreich, Or Meir

Accepted on: 28th October 2007 18:32

Downloads: 3467

Keywords:

An important extension of the proof of the PCP theorem by Irit Dinur (J. ACM 54(3), also ECCC TR05-046) is a gap amplification theorem for Assignment Testers. Specifically, this theorem states that the rejection probability of an Assignment Tester can be amplified by a constant factor, at the expense of increasing the output size of the Assignment Tester by a constant factor. We point out a gap in the proof of this theorem, and show that this gap can be filled.