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
{2i · 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 = 2o(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