vi进i CONTENTS 7.9 Randomized reductions ··...p7.15(129) 7.10 Randomized space-bounded computation .·..·p7.15(129) Chapter notes and history....··..····· p7.17(131) Exercises。。·····················“ p7.18(132) 7.A Random walks and eigenvalues .p7.21(135) 7.A.1 Distributions as vectors and the parameter A(G).·.·.····. .p7.21(135) 7.A.2 Analysis of the randomized algorithm for undirected connectivity. .p7.24(138) 7 B Expander graphs...·..··.······················· .p7.25(139) 7.B.1 The Algebraic Definition.. .p7.25(139) 7.B.2 Combinatorial expansion and existence of expanders.··.····· p7.27(141) 7.B.3 Error reduction using expanders..·..·...·..·..··.·· p7.29(143) 8 Interactive proofs p8.1(147) 8.1 Warmup:Interactive proofs with a deterministic verifier........ p8.1(147) 8.2 The class IP p8.3(149) 8.3 Proving that graphs are not isomorphic.···.··. p8.4(150) 8.4 Public coins and AM................. p8.5(151) 8.4.1 Set Lower Bound Protocol. p8.6(152) Tool:Pairwise independent hash functions. p8.7(153) The lower-bound protocol...·......·····..·····. p8.9(155) 8.4.2 Some properties of IP and AM.................. ·p8.10(156) 8.4.3 Can Gl be NP-complete? p8.11(157) 8.5IP=PSPACE········· .p8.11(157) 8.5.1 Arithmetization..·.· p8.12(158) 8.5.2 Interactive protocol for #SATp p8.12(158) Sumcheck protocol............. p8.13(159) 8.5.3 Protocol for TQBF:proof of Theorem 8.17 p8.14(160) 8.6 The power of the prover .............. p8.15(161) 8.7 Program Checking············· p8.16(162) 8.7.1 Languages that have checkers p8.17(163) 8.8 Multiprover interactive proofs (MIP) .p8.18(164) Chapter notes and history......... .p8.19(165) Exercises ... .p8.20(166) 8.A Interactive proof for the Permanent. .p8.21(167) 8.A.1 The protocol..··.··.·· .p8.23(169) 9 Complexity of counting p9.1(171) 9.1 The class#P.·.· ···p9.2(172) 9.l.1 The class PP:decision-problem analog for#P...··.·. .p9.3(173) 9.2 #P completeness.···· ..p9.4(174) 9.2.1 Permanent and Valiant's Theorem........... .....p9.4(174) 9.2.2 Approximate solutions to#P problems··.··..··.······.·..·p9.8(178) 9.3 Toda's Theorem:PHC P#SAT 。·····························p99(179) Web draft2007-01-0821:59DRAFT viii CONTENTS 7.9 Randomized reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.15 (129) 7.10 Randomized space-bounded computation . . . . . . . . . . . . . . . . . . . . . . . . p7.15 (129) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.17 (131) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.18 (132) 7.A Random walks and eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.21 (135) 7.A.1 Distributions as vectors and the parameter λ(G). . . . . . . . . . . . . . . . . p7.21 (135) 7.A.2 Analysis of the randomized algorithm for undirected connectivity. . . . . . . p7.24 (138) 7.B Expander graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.25 (139) 7.B.1 The Algebraic Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.25 (139) 7.B.2 Combinatorial expansion and existence of expanders. . . . . . . . . . . . . . . p7.27 (141) 7.B.3 Error reduction using expanders. . . . . . . . . . . . . . . . . . . . . . . . . . p7.29 (143) 8 Interactive proofs p8.1 (147) 8.1 Warmup: Interactive proofs with a deterministic verifier . . . . . . . . . . . . . . . . p8.1 (147) 8.2 The class IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.3 (149) 8.3 Proving that graphs are not isomorphic. . . . . . . . . . . . . . . . . . . . . . . . . . p8.4 (150) 8.4 Public coins and AM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.5 (151) 8.4.1 Set Lower Bound Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.6 (152) Tool: Pairwise independent hash functions. . . . . . . . . . . . . . . . . . . . p8.7 (153) The lower-bound protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.9 (155) 8.4.2 Some properties of IP and AM . . . . . . . . . . . . . . . . . . . . . . . . . . p8.10 (156) 8.4.3 Can GI be NP-complete? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.11 (157) 8.5 IP = PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.11 (157) 8.5.1 Arithmetization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.12 (158) 8.5.2 Interactive protocol for #SATD . . . . . . . . . . . . . . . . . . . . . . . . . . p8.12 (158) Sumcheck protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.13 (159) 8.5.3 Protocol for TQBF: proof of Theorem 8.17 . . . . . . . . . . . . . . . . . . . p8.14 (160) 8.6 The power of the prover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.15 (161) 8.7 Program Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.16 (162) 8.7.1 Languages that have checkers . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.17 (163) 8.8 Multiprover interactive proofs (MIP) . . . . . . . . . . . . . . . . . . . . . . . . . . p8.18 (164) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.19 (165) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.20 (166) 8.A Interactive proof for the Permanent . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.21 (167) 8.A.1 The protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.23 (169) 9 Complexity of counting p9.1 (171) 9.1 The class #P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.2 (172) 9.1.1 The class PP: decision-problem analog for #P. . . . . . . . . . . . . . . . . . p9.3 (173) 9.2 #P completeness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.4 (174) 9.2.1 Permanent and Valiant’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . p9.4 (174) 9.2.2 Approximate solutions to #P problems . . . . . . . . . . . . . . . . . . . . . p9.8 (178) 9.3 Toda’s Theorem: PH ⊆ P#SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.9 (179) Web draft 2007-01-08 21:59