The PCP Theorem by
Gap Amplification
Proven by Irit Dinur
Exposition by Radhakrishnan-Sudan
Lecture by Nick Harvey
How to give a proof ?
Verifier
“Is 728950327 prime?”
1




0
3
1
2
0
1
Prover
3 …
Prover writes a proof
Verifier checks all of it.
If theorem is true, Verifier is convinced.
If theorem is false, no proof can convince her.
Probabilistically Checkable Proofs
Lazy verifier
“Is 728950327 prime?”
1




0
3
1
2
0
1
Prover
3 …
Prover writes a proof
Verifier rolls dice; checks a few bits of proof.
If theorem is true, Verifier is convinced.
If theorem is false, Pr[ Verifier is fooled ] < ½.
(This probability is called the Soundness.)
PCP Classes

What theorems can be proven by PCPs?
PCP Classes



What languages can be decided by PCPs?
Depends on # dice, # queries, alphabet size…
The PCP Theorem [Arora, Lund, Motwani, Sudan, Szegedy ‘92]
NP = PCP[ O(log n) dice, O(1) queries,
alphabet size 2, soundness 1/2 ]
Toy PCP Example
Lazy verifier
“Is this graph 3-colorable?”
Prover
Toy PCP Example
Lazy verifier
“Is this graph 3-colorable?”
Prover
Only one bad edge!




Prover produces coloring
Verifier picks a random edge and checks colors
If graph is 3 colorable, Verifier is always convinced
If graph not 3 colorable, Verifier can be fooled.
Prob[ Victor is fooled ] = 1 – O(1/n).
Toy PCP Example
Lazy verifier
“Is this graph 3-colorable?”
Prover
Only one bad edge!




Prover produces coloring
Soundness is too low!
Verifier picks a random edgeWant
and checks
colors
(n)
bad
edges!
GAP
If graph is 3 colorable, Verifier
is always
Want
Gap toconvinced
be (1)!
If graph not 3 colorable, Verifier can be fooled.
Prob[ Verifier is fooled ] = 1 - O(1/n)
Ideal Reduction
{0,1}*
Any NP Language
Graphs on
poly(n) vertices
3 colorable
graphs
L
Transformation T
L


“Far from 3 colorable”
graphs
In every 3 coloring, a constant
No such transformation
fraction of edges are bad
is known.
But we can do something similar!
Generalized Graph Coloring
c{u,v}
Constraint c{u,v}
u’s color
v’s color


0
1
1
1
1
0
0
0
1
G = ( V, E, , C ) where
 is the “alphabet” of colors
C = { ce : e in E } is a set of constraints
where ce : ×  {0,1}
Let GK = { instances with ||=K }.
Generalized Graph Coloring
c{u,v}
Constraint c{u,v}
u’s color
v’s color


0
1
1
1
1
0
0
0
1
G is satisfiable if there is a coloring
satisfying all constraints.
G is -far from satisfiable if every coloring
leaves at least ∙|E| constraints unsatisfied.
Main Theorem

There exists a constant >0
and a polynomial time transformation T s.t.
G16
(generalized graph coloring
instances with ||=16)
{0,1}*
Any NP Language
Satisfiable
graphs
L
Transformation T
L
-far from
satisfiable graphs
Main Theorem

There exists a constant >0
and a polynomial time transformation T s.t.
G16
(generalized graph coloring
instances with ||=16)
All graphs
3-colorable
graphs
Satisfiable
graphs
Transformation T
Non-3-colorable
graphs
-far from
satisfiable graphs
Main Theorem

There exists a constant >0
and a polynomial time transformation
T : graphs  G16 s.t.
3-colorable graphs map to satisfiable graphs
and non-3-colorable graphs map to -far from
satisfiable graphs.
Corollary

NP ⊆ PCP[ O(log n) dice, 2 queries,
alphabet size 16, soundness 1- ]
How To Prove Main Theorem?


Trivial for =O(1/n) (Call  the Gap)
Idea: Find a transformation T that:




Increases gap by a constant factor
Increases # vertices & edges by a constant factor
Maintains alphabet size = 16
Apply T only O(log n) times
Graphs
G16
G16
G16
G16
3-colorable
Satisfiable
Satisfiable
Satisfiable
Satisfiable
Not
3-colorable
-far
'-far
''-far
'''-far
Gap:
1/n

Done!
<

<
'
<
''
<
'''
How To Prove Main Theorem?

Find a transformation T that:




Use bigger constant
Increases gap by a constant factor c∙
Increases # vertices & edges by a constant factor
Maintains alphabet size = 16 We can ignore this!
Handy Lemma [Arora et al.]
There exists a constant >0 such that
for any constant alphabet size K,
there exists a map M : GK  G16
that shrinks gap by a factor .

Pro: Alphabet size shrinks
Con: Gap also shrinks
Dinur’s Goal

Find a transformation T that:




Maps G16  GK, where K is a constant
Increases gap by a large constant factor c
Increases # vertices & edges by a constant factor
Note: 0  gap  1, so the transformation
necessarily fails once gap is large enough.
What to do?

Setup:



Given G=(V,E,,C), construct G’=(V’,E’,’,C’).
Want 2 queries in G’ to somehow test constraints
for many edges in G.
Silly Approach:


Let G’ be the complete graph
Increase the alphabet size to ’=n


Each vertex stores an “opinion” of other vertices’ colors
Constraint in C’ for edge {u,v} checks that
u’s opinions all match v’s opinions, and that
all constraints in C are satisfied.
What to do?
G’
G

Silly Approach:


Let G’ be the complete graph
Increase the alphabet size to ’=n


Much too large!
Each vertex stores an “opinion” of other vertices’ colors
Constraint in C’ for edge {u,v} checks that
u’s opinions all match v’s opinions, and that
all constraints in C are satisfied.
What to do?
Colors of all
nearby vertices

Dinur’s Approach:


Let t be a constant
Each vertex stores “opinions” of its neighbors at distance  t

Want storage at each vertex to be a constant
t
 Vertices should have constant degree d. Storage  16d

Verifier queries two nearby vertices and checks some
of their nearby edges
Implementing Dinur’s Approach



Let t be a large constant
Pick vertex a at random
Do a random walk from a. Halt at each step w.p. 1/t.
B(a,t)
(Ball of radius t
around a)
B(b,t)
e1
a=v0


e2
v1
e3
v2
…
v3
vT=b
E[length of walk]=t
Both a and b have opinions about colors of vertices
in B(a,t) ⋂ B(b,t)
Verifier tests if a’s and b’s opinions agree, and if the
constraints are satisfied on those edges.
When does Verifier reject?



Let t be a large constant
Pick a vertex a at random
Do a random walk.
Stop at each step w.p. 1/t.
FAILURE!
Conflicting Opinions
B(a,t)
B(b,t)
e1
a=v0


e2
v1
e3
v2
…
v3
vT=b
Both a and b have opinions about vertices
in B(a,t) ⋂ B(b,t)
Verifier tests if a’s and b’s opinions agree, and if the
constraints are satisfied on those edges.
When does Verifier reject?



Let t be a large constant
Pick a vertex a at random
Do a random walk.FAILURE!
Stop at each step w.p. 1/t.
Violated Constraint
B(a,t)
B(b,t)
e1
a=v0


e2
v1
e3
v2
…
v3
vT=b
Both a and b have opinions about vertices
in B(a,t) ⋂ B(b,t)
Verifier tests if a’s and b’s opinions agree, and if the
constraints are satisfied on those edges.
Analysis of Dinur’s Approach


If G is satisfiable, then prover supplies valid proof
and verifier accepts with probability 1.
Main Lemma: Let G be -far from satisfiable.
Then verifier rejects every coloring
with probability (∙t) (until  reaches 1/t).


Caveats: (1) G must have constant degree d.
(2) G must have good expansion.
Corollary: Dinur’s goal is achieved! (Modulo caveats)
We have a transformation T that:



Maps G16
t
d
 GK, where K16
Increases gap by a factor t
Increases # vertices & edges by a constant factor
View of Dinur’s Transformation
G’
G
New Edges
(connect vertices at distance  t)
Corollary: Dinur’s goal is achieved! (Modulo caveats)



We have a transformation T that:
t
Maps G16  GK, where K16d
Increases gap by a factor t
Increases # vertices & edges by a constant factor
Remaining tasks for this talk



Proof of Main Lemma
Transforming graphs to constant degree
Transforming graphs to expanders
Postpone
until end
Breaktime Puzzle!


I have two (biased) dice Da and Db
Say their outcomes have probabilities:


a1  a2  …  a6
b4  b2  …  b5
where Σi ai = 1
where Σi bi = 1
(ordering is irrelevant)


Roll Da and Db once each, independently
What is Pr[ outcomes differ ]?
(I want a very simple lower bound, depending on ai’s & bi’s)
Review of first half
Map graph 3-coloring to generalized graph coloring in G16
Graphs
G16
G16
G16
G16
3-colorable
Satisfiable
Satisfiable
Satisfiable
Satisfiable
Not
3-colorable
-far
'-far
''-far
'''-far
Gap:
1/n
Want
<

<
'
<
''
<
a transformation T that:
Maps G16  GK, where K is a constant
Increases gap by a large constant factor c
Increases # vertices & edges by a constant factor

'''
Analysis of Dinur’s Approach




Suppose G is -far from satisfiable
Let A’ be any coloring of G’
Want to show: Pr[ verifier detects fault in G’ ]  (∙t)
How?




Show that A’ induces a coloring A of G
A has many faulty edges by assumption
Show that faults in A also cause A’ to have faults
Formally:




Let N be an RV = # faulty edges of G detected by verifier
Want to show: Pr[ N>0 ]  (∙t)
Via second-moment method: Pr[ N>0 ]  E[ N ]2 / E[ N2 ]
Will show E[ N ] is large and E[ N2 ] is small
Remaining Tasks

Define coloring A of G induced by coloring A’ of G’


Let F be { faulty edges of coloring A }
Let N be an RV = # edges of F detected by verifier

Show E[ N ]  ( t∙|F| / |E| )

Show E[ N2 ]  O( t∙|F| / |E| )

E[ N ]2
Thus Pr[ N>0 ] 
 ( t∙|F| / |E| )  (t∙)
2
E[ N ]
(end of
Main Lemma)
Induced Coloring A

Notation:



A’u(v) = u’s opinion of v’s color in coloring A’
A(v) = v’s color in A
Intuition for defining A:


Color A(u) should be a “majority opinion” of u’s color in A’
Definition of A should be easy to analyze
when considering verifier’s behavior


Verifier uses random walk  define A via random walk
Formally:



Perform random walk of length  t-1 from v in G’.
Let final vertex be u. Then u votes for color A’u(v).
Let A(v) be the majority vote.
How to pick A(v)?
A’s(v)
r
Votes for v’s color
z
s
A’z(v)
y
R
G
B
16
3
1
1
w
u
x
Set A(v) = Red
v

Formally:



Perform random walk of length  t-1 from v in G’.
Let final vertex be u. Then u votes for color A’u(v).
Let A(v) be the majority vote.
Remaining Tasks

Define coloring A of G induced by coloring A’ of G’


Let F be { faulty edges of coloring A }
Let N be an RV = # edges of F detected by verifier

Show E[ N ]  ( t∙|F| / |E| )

Show E[ N2 ]  O( t∙|F| / |E| )

E[ N ]2
Thus Pr[ N>0 ] 
 ( t∙|F| / |E| )  (t∙)
2
E[ N ]
(end of
Main Lemma)
E[ N ] is large

Focus on a single edge e∈F
a

u
…
v
B(b,t)
b
Suppose walk traverses e and {u,v} ⊆ B(a,t) ⋂ B(b,t)
Verifier performs 3 tests:
Test 1
Is A’a(u) = A’b(u)?

e
…
B(a,t)

Let F be { faulty edges of coloring A }
Let N be an RV = # edges of F detected by verifier
Test 2
Is A’a(v) = A’b(v)?
Test 3
Is ce( A’a(u), A’b(v) )=1?
Intuition


If opinions of nearby vertices differ then Tests 1 and 2 will fail
If opinions of nearby vertices match then Test 3 will fail
E[ N ] is large

Focus on a single edge e∈F
a

Is A’a(u) = A’b(u)?

u
…
v
B(b,t)
b
Suppose walk traverses e and {u,v} ⊆ B(a,t) ⋂ B(b,t)
Verifier performs 3 tests:
Test 1

e
…
B(a,t)

Let F be { faulty edges of coloring A }
Let N be an RV = # edges of F detected by verifier
Test 2
Is A’a(v) = A’b(v)?
Test 3
Is ce( A’a(u), A’b(v) )=1?
Pr[ verifier detects fault ]  maxi Pr[ Test i detects fault ]
Define: pu = Pr[ A’a(u) = A(u) | d(a,u)<t ]
Unknown
parameters
pv = Pr[ A’b(v) = A(v) | d(b,v)<t ]
E[ N ] is large

Verifier performs 3 tests:
Test 1
Is A’a(u) = A’b(u)?

Test 2
Is A’a(v) = A’b(v)?
Test 3
Is ce( A’a(u), A’b(v) )=1?
Define: pu = Pr[ A’a(u) = A(u) | d(a,u)<t ]
(Unknown)
Pr[ Test 1 detects fault ]
 Pr[ d(a,u)<t  d(b,v)<t  Test 1 detects fault ]
 (1-1/e)2 Pr[ Test 1 detects fault | d(a,u)<t  d(b,v)<t ]
= (1-1/e)2 Pr[ A’a(u)A’b(u) | d(a,u)<t  d(b,v)<t ]
Roll two independent, biased dice Da and Db.
What is Pr[ values differ ]?
 (1 – (prob of most likely value for Da)
E[ N ] is large

Verifier performs 3 tests:
Test 1
Test 2
Is A’a(u) = A’b(u)?

Is A’a(v) = A’b(v)?
Test 3
Is ce( A’a(u), A’b(v) )=1?
Define: pu = Pr[ A’a(u) = A(u) | d(a,u)<t ]
(Unknown)
Pr[ Test 1 detects fault ]
 Pr[ d(a,u)<t  d(b,v)<t  Test 1 detects fault ]
 (1-1/e)2 Pr[ Test 1 detects fault | d(a,u)<t  d(b,v)<t ]
= (1-1/e)2 Pr[ A’a(u)A’b(u) | d(a,u)<t  d(b,v)<t ]
 (1 – (prob of most likely value for Da)
By definition, A(u) is the most likely value for A’a(u)!
 (1-1/e)2 (1-pu)
E[ N ] is large

Verifier performs 3 tests:
Test 1
Test 2
Is A’a(u) = A’b(u)?

Is A’a(v) = A’b(v)?
Test 3
Is ce( A’a(u), A’b(v) )=1?
Define: pu = Pr[ A’a(u) = A(u) | d(a,u)<t ]
pv = Pr[ A’b(v) = A(v) | d(b,v)<t ]
Unknown
Pr[ Test 3 detects fault ]
 Pr[ d(a,u)<t  d(b,v)<t  Test 3 detects fault ]
 (1-1/e)2 Pr[ Test 3 detects fault | d(a,u)<t  d(b,v)<t ]
 (1-1/e)2 Pr[ A’a(u)=A(u)  A’b(v)=A(v) | d(a,u)<t  d(b,v)<t ]
=
(1-1/e)2
pu pv
a and b are independent
E[ N ] is large

Verifier performs 3 tests:
Test 1
Is A’a(u) = A’b(u)?

Test 2
Is A’a(v) = A’b(v)?
Test 3
Is ce( A’a(u), A’b(v) )=1?
Define: pu = Pr[ A’a(u) = A(u) | d(a,u)<t ]
pv = Pr[ A’b(v) = A(v) | d(b,v)<t ]
Unknown
Pr[ Test 1 detects fault ]  (1-1/e)2 (1-pu)
Pr[ Test 2 detects fault ]  (1-1/e)2 (1-pv)
Pr[ Test 3 detects fault ]  (1-1/e)2 pu pv
Pr[ Verifier detects fault ]  maxi Pr[ Test i detects fault ]
 (1-1/e)2 max { 1-pu, 1-pv, pupv }
 (1-1/e)2 ( √5 - 1) / 2  1/8
E[ N ] is large

Verifier performs 3 tests:
Test 1
Is A’a(u) = A’b(u)?

Test 2
Is A’a(v) = A’b(v)?
Test 3
Is ce( A’a(u), A’b(v) )=1?
Define: pu = Pr[ A’a(u) =
A(u) | d(a,u)<t ]
Punchline
Unknown
pv = Pr[ A’b(v) = A(v) | d(b,v)<t ]
e is a faulty edge for G under coloring A
Pr[
1 detects
fault
] traverses
(1-1/e)2 (1-p
If Test
verifier’s
random
walk
e, u)
Pr[ itTest
detects
faultwith
]  probability
(1-1/e)2 (1-p
then
will 2detect
a fault
1/8.
v)
Pr[ Test 3 detects fault ]  (1-1/e)2 pu pv
Pr[ Verifier detects fault ]  maxi Pr[ Test i detects fault ]
 (1-1/e)2 max { 1-pu, 1-pv, pupv }
 (1-1/e)2 ( √5 - 1) / 2  1/8
Wrapup: E[ N ] is large

Notation:



Let F be { faulty edges of coloring A }
Let N be an RV = # edges of F detected as faulty by verifier
Focus on a single edge e∈F



Let Me = # times e is traversed by verifier’s random walk
Let Ne = # times e is traversed by verifier’s random walk
and is detected to be faulty
Thus N = Σe∈F Ne
E[ Ne ] = E[ Ne | Me=0 ]∙Pr[ Me=0 ] + E[ Ne | Me1 ]∙Pr[ Me1 ]
 (1/8)∙E[ Me | Me1 ]∙Pr[ Me1 ] = (1/8)∙E[ Me ]
= (1/8)∙E[ length of random walk ] / |E|
= (1/8) ∙ t / |E|

E[ N ] = Σe∈F E[ Ne ] = t∙|F| / 8∙|E|= ∙t / 8
ith edge of walk is
distributed uniformly
since G is regular
Remaining Tasks

Define coloring A of G induced by coloring A’ of G’


Let F be { faulty edges of coloring A }
Let N be an RV = # edges of F detected by verifier

Show E[ N ]  ( t∙|F| / |E| )

Show E[ N2 ]  O( t∙|F| / |E| )

E[ N ]2
Thus Pr[ N>0 ] 
 ( t∙|F| / |E| )  (t∙)
2
E[ N ]
(end of
Main Lemma)
E[ N2 ] is small



Let e1, e2, …, be edges chosen by verifier
Let i be indicator that  i edges chosen and ei ∈ F
Simplifying Assumption:

Edges chosen independently, not by random walk
 Pr[j=1| i=1] = (1-1/t)j-i |F|/|E|
(if j>i)
E[N2] = E[ (∑i1 i)2 ]
 2 ∑ji E[ i j ]
= 2 ∑i1Pr[i=1] ∑ji Pr[j=1| i=1]
= 2 ( t∙|F| / |E| ) ( 1 + ∑k1 (1-1/t)k |F|/|E| )
< 2 ( t∙|F| / |E| ) ( 1 + t |F| / |E| )
< 4 ( t∙|F| / |E| )
So long as =|F|/|E|<1/t
E[ N2 ] is small



Let e1, e2, …, be edges chosen by verifier
Let i be indicator that  i edges chosen and ei ∈ F
Claim: If G is an expander then ei’s on random walk
are almost pairwise independent.

Pr[j=1| i=1] = (1-1/t)j-i ( |F|/|E| + (1-2/d2)j-i-1 )
E[N2]
(∑i1 i)2
(if j>i)
Expansion of G
= E[
]
 2 ∑ji E[ i j ]
= 2 ∑i1Pr[i=1] ∑ji Pr[j=1| i=1]
= 2 ( t∙|F| / |E| ) (1 + ∑k1 (1-1/t)k (|F|/|E|+(1-2/d2)k-1) )
< 2 ( t∙|F| / |E| ) (1 + t |F|/|E| + 2/d2 )
< 4 ( t∙|F| / |E| ) (1 + 2/d2)
E[ N2 ] is small



Let e1, e2, …, be edges chosen by verifier
Let i be indicator that  i edges chosen and ei ∈ F
Claim: If G is an expander then ei’s on random walk
are almost pairwise independent.

Pr[ej∈F | e1∈F] = |F|/|E| + (1-2/d2)j-2
(if j>1)
E[N2] = E[ (∑i1 i)2 ]
 2 ∑ji E[ i j ]
= 2 ∑i1Pr[i=1] ∑ji Pr[j=1| i=1]
= 2 ( t∙|F| / |E| ) (1 + ∑k1 (1-1/t)k (|F|/|E|+(1-2/d2)k-1) )
< 2 ( t∙|F| / |E| ) (1 + t |F|/|E| + 2/d2 )
< 4 ( t∙|F| / |E| ) (1 + 2/d2)
Remaining Tasks

Define coloring A of G induced by coloring A’ of G’


Let F be { faulty edges of coloring A }
Let N be an RV = # edges of F detected by verifier

Show E[ N ]  ( t∙|F| / |E| )

Show E[ N2 ]  O( t∙|F| / |E| )

Claim: If G is an expander then ei’s on random walk
are almost pairwise independent.


Pr[ej∈F | e1∈F] = |F|/|E| + (1-2/d2)j-2
(if j>1)
Thus Pr[ N>0 ]  E[ N ]2  ( t∙|F| / |E| )  (t∙)
E[ N2 ]
(end of
Main Lemma)
Random Walks on Expanders



Claim: Pr[ej∈F | e1∈F] = |F|/|E| + (2/d)j-2 (if j>1)
Notation:

2  d-2/d is the second-largest eigenvalue

F(v) = { edges in F incident on v }

v1, v2, … are the vertices on random walk

i is the distribution on vi, conditioned on e1∈F

M is transition matrix of the random walk
Preliminaries:
1)
1(v) = F(v) / 2|F|
2)
1 = (1/n)∙1 + F’ / 2|F|
where F’ is component of F orthogonal to 1
3)
j-1 = Mj-2 1 = Mj-2 ( (1/n)∙1 + F’ / 2|F| )
4)
Pr[ej∈F | e1∈F] = ∑v (F(v)/d)∙j-1(v) = (FT j-1)/d
Random Walks on Expanders
1)
2)
3)
4)
1(v) = F(v) / 2|F|
1 = (1/n)∙1 + F’ / 2|F|
j-1 = Mj-2 1 = Mj-2 ( (1/n)∙1 + F’ / 2|F| )
Pr[ej∈F | e1∈F] = ∑v (F(v)/d)∙j-1(v) = (FT j-1)/d
Pr[ej∈F | e1∈F] = (FT j-1)/d
(from (4))
= (FT Mj-2 ( (1/n)∙1 + F’/2|F| ) ) / d
(from (3))
= (1/nd)∙FT 1 + (1/2|F|d) FT Mj-2 F’
(linearity)
 |F|/|E| + (1/2|F|d) ||F|| ||Mj-2 F’||
(Cauchy-Schwarz)
 |F|/|E| + (1/2|F|d) ||F|| (2/d)j-2 ||F|| (since F’ ┴ 1)
= |F|/|E| + (1/2|F|d) (2/d)j-2 (∑v F(v)2)
 |F|/|E| + (1/2|F|d) (2/d)j-2 (d ∑v F(v))
= |F|/|E| + (2/d)j-2
(end of Claim)
Remaining tasks for this talk



Proof of Main Lemma
Transforming graphs to constant degree
Transforming graphs to expanders
Transforming Graphs to Constant Degree
Introduce dummy
vertices!
v
Transforming Graphs to Constant Degree
Want to force
dummies
to have same color
Transforming Graphs to Constant Degree
Clique?
Degree too large!
Too many edges
Add constraints
forcing equality
Transforming Graphs to Constant Degree
Cycle?
Half vertices can half
wrong color but only
two violated edges.
Want a graph
where cuts
have many edges
Transforming Graphs to Constant Degree
Expander?
Just right!
Transforming Graphs to Expanders
G is not an expander
H is an expander
Transforming Graphs to Expanders
G  H is an expander
Descargar

The PCP Theorem by Gap Amplification