A generalized graph k-coloring
problem has as an instance a graph
G = (V, E) and constraint functions
p : { 1,…,k} × { 1,…,k} ® {accept, Before getting a little into the de-
e
reject} for every edge e Î E. The tails of the proof of this lemma, let us
canonical 2IP verifier for in instance note that it suffices to prove the PCP
expects as provers two oracles giving theorem.
c , c : V ® { 1,…, k} and does one of
12
the following: With probability 1/2 it
picks a random edge e = (u, v) Î E que-
ries for c (u) and c (v) and accepts iff
12
p (c (u), c (v)) = accept. With prob-
e1 2
ability 1/2 it picks a random vertex
u Î V and queries for c (u) and c (u)
12
and accepts if and only if c (u) = c (v).
12
Note that the canonical 2IP verifier
has answer size [log k]. An instance is
2
satisfiable if the canonical 2IP verifier
accepts with probability 1. An instance
is e -unsatisfiable if the probability that
the verifier rejects is at least e .

Key to Dinur’s iterations are transformations among generalized graph coloring problems that play with the gap and the answer size (that is, of colors allowed) of the 2IP verifiers. Since these transformations are applied many times to some fixed starting instance, it is important that the transformations do not increase the problem size by much and Dinur insists that they only increase them by a linear factor. We define this notion formally here.

there exists a polynomial-time computable ( 3, 3, 2, e )-linear-transformation T.

0

Lemma 4. 8 (Answer-Reduction). For every k there exists a constant b >

2

0 such that for every K < ∞ a (K, k, b , 1)-

2

linear-transformation T exists.

2

 

Proof of Theorem 2. 2. We describe a 2IP verifier for 3SAT. The verifier acts as follows. Given a 3CNF formula f of length n, it first applies the standard reduction from 3SAT to 3-coloring to get an instance G of (generalized)

0
graph 3-coloring which is 3-colorable
iff f is satisfiable. Note that this in-
stance is 1/m-unsatisfiable for some
m = O(n). The verifier then iteratively
applies the transformation T to G  =
0
log m times, that is, it sets G = T(G )
i i− 1
for i = 1,…,. Finally it simulates the
canonical 2IP verifier on input G .



The constant b obtained from the
2
lemma is quite small (very close to 0).
But for this price in gap-reduction we
can go from large answer sizes to small
ones, and the price we pay in the un-
satisfiability is independent of K This
allows us to combine the two lemmas
to get the powerful gap amplification
lemma as follows.

 

Proof of Lemma 4. 6. Fix k = 3. Let b
2
and T be as in Lemma 4. 8. Apply Lem-
2
ma 4. 7 with b = 2/b and let K, e and T
12 1 1
be as guaranteed by Lemma 4. 7. Let T(G)
= T (T (G) ). Then, it can be verified that T
21
is a (k, k, 2, b · e )-linear-transformation.
21

 

Definition 4. 5. A transformation T that maps instances of generalized graph k-coloring to generalized graph K-coloring is a (k, K, b, e )-linear-transformation if it

0

satisfies the following properties:

˲ T(G) has size linear in the size of G.

˲ T(G) is satisfiable if G is satisfiable.

˲ T(G) is min{b e , e }-unsatisfiable if

.

0

G is e -unsatisfiable.

Note that the parameter b above may be greater than 1 or smaller; and the effect in the two cases is quite different. If b > 1 then the transformation increases the gap, while if b < 1 then the transformation reduces the gap. As we will see below, Dinur’s internal lemmas play with effects of both kinds (combining them in a very clever way).

The key lemma in Dinur’s iterations does not play with the answer size and simply increase the gap and may be stated as below.

If f is satisfiable, then so is G i for every i, and so the canonical 2IP verifier accepts with probability 1. If f is unsatisfiable then G is min i

{2ⁱ · 1/m, e }-unsatisfiable and so G is e -
0 0
unsatisfiable. Finally note that since each
iteration increases the size of G only by a
i
constant factor, the final graph G is only



polynomially larger than f, and the entire process only requires polynomial time.

Note that the 2IP verifier thus constructed has answer size [log 3] = 2 bits.

2

Its gap is e . The conversion to a PCP
0
verifier leads to one that has query com-
plexity of 4 bits and gap e > 0.

0

We now turn to the magical gap-amplifying lemma above. Dinur achieves this lemma with two sub-lem-mas, where the game between answer size and gap becomes clear.

 

Lemma 4. 7 (Gap-Increase). For every k,

b < ∞, there exists a constant K < ∞ and e 11

> 0 such that a (k, K, b , e )-linear-transfor-

11

mation T exists.

1

 

Lemma 4. 6 (Gap Amplification Lemma). There exists a constant e > 0 such that

0

Note that a large b >> 1 implies the

1

transformation enhances the unsatisfiability of an instance. The Gap-Increase lemma is claiming that one can enhance this unsatisfiability by any constant factor for an appropriate price in the answer size. The next lemma trades off in the other direction, but with a clever and critical switch of quantifiers.

Finally we comment on the proofs of Lemmas 4. 7 and 4. 8. We start with the latter. The crux here is the independence of b and K. A reader who attempts

2 to use standard reductions, from say k-coloring to K-coloring would realize that this is nontrivial to achieve. But if one were to ignore the linear-size restriction, the PCP literature already gave such transformations before. In particular Lemma 4. 4 gives such a transformation provided K = 2^{o(log n)}. When specialized to the case K = O( 1) the reduction also turns out to be a linear one.

Lemma 4. 7 is totally novel in Dinur’s works. ^{12, 13} To get a sense of this lemma, let us note that its principal goal is to reduce the error of the 2IP verifier and so is related to the standard question in the context of randomized algorithms: that of error-reduction. In the context of randomized algorithms this is well studied. If one starts with any randomized algorithm to compute some function and say it produces the right answer with probability 2/3 (and errs with probability 1/3), then one can reduce the error by running this algorithm many times and output-ting the most commonly seen answer. Repetition m times reduces the error to 2^−Ω(m). One could view a 2IP verifier as just another randomized procedure and attempt to repeat the actions of the verifier m times to reduce its error. This leads to two problems. First the natural approach increases the number of rounds of communication