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 K16 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 K16d 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 | Me1 ]∙Pr[ Me1 ] (1/8)∙E[ Me | Me1 ]∙Pr[ Me1 ] = (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[ (∑i1 i)2 ] 2 ∑ji E[ i j ] = 2 ∑i1Pr[i=1] ∑ji Pr[j=1| i=1] = 2 ( t∙|F| / |E| ) ( 1 + ∑k1 (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] (∑i1 i)2 (if j>i) Expansion of G = E[ ] 2 ∑ji E[ i j ] = 2 ∑i1Pr[i=1] ∑ji Pr[j=1| i=1] = 2 ( t∙|F| / |E| ) (1 + ∑k1 (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[ (∑i1 i)2 ] 2 ∑ji E[ i j ] = 2 ∑i1Pr[i=1] ∑ji Pr[j=1| i=1] = 2 ( t∙|F| / |E| ) (1 + ∑k1 (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