REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR05-046 | 26th September 2005 00:00

#### The PCP Theorem by gap amplification

Revision #1
Authors: Irit Dinur
Accepted on: 26th September 2005 00:00
Keywords:

Abstract:

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).

### Paper:

TR05-046 | 17th April 2005 00:00

#### The PCP theorem by gap amplification

TR05-046
Authors: Irit Dinur
Publication: 17th April 2005 02:37
Keywords:

Abstract:

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).

### Comment(s):

Comment #1 to TR05-046 | 3rd June 2005 19:18

#### Gap Amplification Fails Below 1/2 Comment on: TR05-046

Comment #1
Authors: Andrej Bogdanov
Accepted on: 3rd June 2005 19:18
Keywords:

Abstract:

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 to TR05-046 | 4th November 2005 09:38

#### Gap amplification using lazy random walks Comment on: TR05-046

Comment #2
Accepted on: 4th November 2005 09:38
Keywords:

Abstract:

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 to TR05-046 | 28th October 2007 18:32

#### A Small Gap in the Gap Amplification of Assignment Testers

Comment #3
Authors: Oded Goldreich, Or Meir
Accepted on: 28th October 2007 18:32