《理论计算机科学》课程教学资源（阅读文献）Computational Complexity - A Modern Approach

CONTENTS vii 5 The Polynomial Hierarchy and Alternations p5.1(91) 5.1 The classes >2 and........·..·· ....p5.1(91) 5.2 The polynomial hierarchy....... 。。 p5.3(93) 5.2.1 Properties of the polynomial hierarchy. p5.3(93) 5.2.2 Complete problems for levels of PH .p5.4(94) 5.3 Alternating Turing machines ·p5.5(95) 5.3.1 Unlimited number of alternations? p5.6(96) 5.4 Time versus alternations:time-space tradeoffs for SAT.. p5.6(96) 5.5 Defining the hierarchy via oracle machines. .p5.8(98) Chapter notes and history.············ p5.9(99) Exercises p5.10(100) 6 Circuits p6.1(101) 6.1 Boolean circuits.....··.······· ··..p6.1(101) 6.1.1 Turing machines that take advice p6.5(105) 6.2 Karp-Lipton Theorem p6.6(106 6.3 Circuit lowerbounds 。。 p6.7(107) 6.4 Non-uniform hierarchy theorem ... p6.8(108) 6.5 Finer gradations among circuit classes p6.8(108) 6.5.1 Parallel computation and NC p6.9(109) 6.5.2P-completeness.·..······. .p6.10(110) 6.6 Circuits of exponential size 。，。。 p6.11(111) 6.7 Circuit Satisfiability and an alternative proof of the Cook-Levin Theorem.... p6.12(112) Chapter notes and history,································ p6.13(113) Exercises p6.13(113) 7 Randomized Computation p7.1(115) 7.1 Probabilistic Turing machines . ··.·p7.2(116) 7.2 Some examples of PTMs.............··.. p7.3(117) 7.2.1 Probabilistic Primality Testing....··.·. p7.3(117）) 7.2.2 Polynomial identity testing..·.··.·.·- p7.4(118 7.2.3 Testing for perfect matching in a bipartite graph. p7.5(119) 7.3 One-sided and zero-sided error:RP,coRP,ZPP p7.6(120) 7.4 The robustness of our definitions.....········· p7.7(121) 7.4.1 Role of precise constants,error reduction. .p7.7(121) 7.4.2 Expected running time versus worst-case running time..···. ·p7.10(124) 7.4.3 Allowing more general random choices than a fair random coin.... .p7.10(124) 7.5 Randomness efficient error reduction.. ,p7.11(125) 7.6 BPP C P/poly .p7.12(126) 7.7 BPP is in PH .p7.13(127) 7.8 State of our knowledge about BPP......... p7.14(128) Complete problems for BPP?...... ..p7.14(128) Does BPTIME have a hierarchy theorem?··············· .p7.15(129) Wab.draft2007-01-0821:59

DRAFT CONTENTS vii 5 The Polynomial Hierarchy and Alternations p5.1 (91) 5.1 The classes Σ p 2 and Π p 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.1 (91) 5.2 The polynomial hierarchy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.3 (93) 5.2.1 Properties of the polynomial hierarchy. . . . . . . . . . . . . . . . . . . . . . . p5.3 (93) 5.2.2 Complete problems for levels of PH . . . . . . . . . . . . . . . . . . . . . . . p5.4 (94) 5.3 Alternating Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.5 (95) 5.3.1 Unlimited number of alternations? . . . . . . . . . . . . . . . . . . . . . . . . p5.6 (96) 5.4 Time versus alternations: time-space tradeoffs for SAT. . . . . . . . . . . . . . . . . . p5.6 (96) 5.5 Defining the hierarchy via oracle machines. . . . . . . . . . . . . . . . . . . . . . . . p5.8 (98) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.9 (99) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.10 (100) 6 Circuits p6.1 (101) 6.1 Boolean circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.1 (101) 6.1.1 Turing machines that take advice . . . . . . . . . . . . . . . . . . . . . . . . . p6.5 (105) 6.2 Karp-Lipton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.6 (106) 6.3 Circuit lowerbounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.7 (107) 6.4 Non-uniform hierarchy theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.8 (108) 6.5 Finer gradations among circuit classes . . . . . . . . . . . . . . . . . . . . . . . . . . p6.8 (108) 6.5.1 Parallel computation and NC . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.9 (109) 6.5.2 P-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.10 (110) 6.6 Circuits of exponential size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.11 (111) 6.7 Circuit Satisfiability and an alternative proof of the Cook-Levin Theorem . . . . . . p6.12 (112) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.13 (113) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.13 (113) 7 Randomized Computation p7.1 (115) 7.1 Probabilistic Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.2 (116) 7.2 Some examples of PTMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.3 (117) 7.2.1 Probabilistic Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . . . p7.3 (117) 7.2.2 Polynomial identity testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.4 (118) 7.2.3 Testing for perfect matching in a bipartite graph. . . . . . . . . . . . . . . . . p7.5 (119) 7.3 One-sided and zero-sided error: RP, coRP, ZPP . . . . . . . . . . . . . . . . . . . p7.6 (120) 7.4 The robustness of our definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.7 (121) 7.4.1 Role of precise constants, error reduction. . . . . . . . . . . . . . . . . . . . . p7.7 (121) 7.4.2 Expected running time versus worst-case running time. . . . . . . . . . . . . p7.10 (124) 7.4.3 Allowing more general random choices than a fair random coin. . . . . . . . . p7.10 (124) 7.5 Randomness efficient error reduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.11 (125) 7.6 BPP ⊆ P/poly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.12 (126) 7.7 BPP is in PH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.13 (127) 7.8 State of our knowledge about BPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.14 (128) Complete problems for BPP? . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.14 (128) Does BPTIME have a hierarchy theorem? . . . . . . . . . . . . . . . . . . . p7.15 (129) Web draft 2007-01-08 21:59

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:59

DRAFT 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

CONTENTS i议 9.3.1 The class P and hardness of satisfiability with unique solutions. ······p9.9(179) Proof of Theorem9.l5.·..·.···. p9.11(181) 9.3.2Step1:Randomized reduction from PH to⊕P.....·...·.·..·. p9.11(181) 9.3.3 Step 2:Making the reduction deterministic........... .p9.13(183) 9.4 Open Problems......·.....··.··.· .p9.14(184 Chapter notes and history ..... p9.14(184) Exercises......··. p9.15(185) 10 Cryptography p10.1(187） 10.1 Hard-on-average problems and one-way functions .. ···.·p10.2(188) l0.l.1 Discussion of the definition of one-way function,········ p10.4(190) l0.l.2 Random self-reducibility.............·.··..··.· p10.5(191) l0.2 What is a random-enough string？..·...·. p10.5(191) 10.2.1 Blum-Micali and Yao definitions p10.6(192 10.2.2 Equivalence of the two definitions........ .p10.8(194) 10.3 One-way functions and pseudorandom number generators p10.10(196 l0.3.1 Goldreich-Levin hardcore bit.............·.···· p10.10(196) 10.3.2 Pseudorandom number generation p10.13(199) l0.4 Applications.·················· .p10.13(199 10.4.1 Pseudorandom functions.... p10.13(199) 10.4.2 Private-key encryption:definition of security p10.14(200) l0.4.3 Derandomization..............·.·.····.··· p10.15(201) 10.4.4 Tossing coins over the phone and bit commitment p10.16(202) l0.4.5 Secure multiparty computations.·.....···.··. p10.16(202) 10.4.6 Lowerbounds for machine learning ,p10.17(203) 10.5 Recent developments..··.·····.· p10.17(203) Chapter notes and history p10.17(203) Exercises .p10.18(204) II Lowerbounds for Concrete Computational Models p10.21(207) 11 Decision Trees p11.2(211) 11.1 Certificate Complexity ... ·..·p11.4(213) 11.2 Randomized Decision Trees p11.6(215) 11.3 Lowerbounds on Randomized Complexity p11.6(215) 11.4 Some techniques for decision tree lowerbounds. p11.8(217) 11.5 Comparison trees and sorting lowerbounds... p11.9(218) ll.6Yao's MinMax Lemma.·.········· .p11.9(218) Exercises p11.9(218) Chapter notes and history p11.10(219) Web draft2007-01-0821:59

DRAFT CONTENTS ix 9.3.1 The class ⊕P and hardness of satisfiability with unique solutions. . . . . . . p9.9 (179) Proof of Theorem 9.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.11 (181) 9.3.2 Step 1: Randomized reduction from PH to ⊕P . . . . . . . . . . . . . . . . . p9.11 (181) 9.3.3 Step 2: Making the reduction deterministic . . . . . . . . . . . . . . . . . . . p9.13 (183) 9.4 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.14 (184) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.14 (184) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.15 (185) 10 Cryptography p10.1 (187) 10.1 Hard-on-average problems and one-way functions . . . . . . . . . . . . . . . . . . . . p10.2 (188) 10.1.1 Discussion of the definition of one-way function . . . . . . . . . . . . . . . . . p10.4 (190) 10.1.2 Random self-reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.5 (191) 10.2 What is a random-enough string? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.5 (191) 10.2.1 Blum-Micali and Yao definitions . . . . . . . . . . . . . . . . . . . . . . . . . p10.6 (192) 10.2.2 Equivalence of the two definitions . . . . . . . . . . . . . . . . . . . . . . . . . p10.8 (194) 10.3 One-way functions and pseudorandom number generators . . . . . . . . . . . . . . . p10.10 (196) 10.3.1 Goldreich-Levin hardcore bit . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.10 (196) 10.3.2 Pseudorandom number generation . . . . . . . . . . . . . . . . . . . . . . . . p10.13 (199) 10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.13 (199) 10.4.1 Pseudorandom functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.13 (199) 10.4.2 Private-key encryption: definition of security . . . . . . . . . . . . . . . . . . p10.14 (200) 10.4.3 Derandomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.15 (201) 10.4.4 Tossing coins over the phone and bit commitment . . . . . . . . . . . . . . . p10.16 (202) 10.4.5 Secure multiparty computations . . . . . . . . . . . . . . . . . . . . . . . . . p10.16 (202) 10.4.6 Lowerbounds for machine learning . . . . . . . . . . . . . . . . . . . . . . . . p10.17 (203) 10.5 Recent developments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.17 (203) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.17 (203) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.18 (204) II Lowerbounds for Concrete Computational Models p10.21 (207) 11 Decision Trees p11.2 (211) 11.1 Certificate Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.4 (213) 11.2 Randomized Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.6 (215) 11.3 Lowerbounds on Randomized Complexity . . . . . . . . . . . . . . . . . . . . . . . . p11.6 (215) 11.4 Some techniques for decision tree lowerbounds . . . . . . . . . . . . . . . . . . . . . . p11.8 (217) 11.5 Comparison trees and sorting lowerbounds . . . . . . . . . . . . . . . . . . . . . . . . p11.9 (218) 11.6 Yao’s MinMax Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.9 (218) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.9 (218) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.10 (219) Web draft 2007-01-08 21:59

X CONTENTS 12 Communication Complexity p12.1(221) 12.1 Definition........··. ···.·p12.1(221) 12.2 Lowerbound methods.··. p12.2(222) 12.2.1 Fooling set p12.2(222) 12.2.2 The tiling lowerbound p12.3(223 12.2.3 Rank lowerbound..... ,p12.4(224) 12.2.4 Discrepancy...···· .p12.5(225) A technique for upperbounding the discrepancy. ,p12.6(226) 12.2.5 Comparison of the lowerbound methods·········· p12.7(227) 12.3 Multiparty communication complexity p12.8(228) Discrepancy-based lowerbound p12.9(229) 12.4 Probabilistic Communication Complexity p12.10(230) 12.5 Overview of other communication models p12.10(230) 12.6 Applications of communication complexity p12.11(231) Exercises p12.11(231) Chapter notes and history p12.12(232) 13 Circuit lowerbounds p13.1(235) 13.1 ACo and Hastad's Switching Lemma..... p13.1(235) 13.1.1 The switching lemma p13.2(236) 13.1.2 Proof of the switching lemma (Lemma 13.2) .p13.3(237) l3.2 Circuits With“Counters”:ACC... p13.5(239) 13.3 Lowerbounds for monotone circuits. p13.8(242) 13.3.1 Proving Theorem13.9····· p13.8(242) Clique Indicators..···.······· p13.8(242) Approximation by clique indicators. p13.9(243) 13.4 Circuit complexity:The frontier p13.11(245) 13.4.1 Circuit lowerbounds using diagonalization... p13.11(245) 13.4.2 Status of ACC versus P....... p13.12(246) 13.4.3 Linear Circuits With Logarithmic Depth p13.13(247) 13.4.4 Branching Programs p13.13(247) 13.5 Approaches using communication complexity 。 p13.14(248) 13.5.1 Connection to ACCo Circuits.... p13.14(248) 13.5.2 Connection to Linear Size Logarithmic Depth Circuits p13.15(249) l3.5.3 Connection to branching programs··.·····. p13.15(249) 13.5.4 Karchmer-Wigderson communication games and depth lowerbounds p13.15(249) Chapter notes and history······························· p13.17(251) Exercises 。。。。 p13.18(252) 14 Algebraic computation models p14.1(255) 14.1 Algebraic circuits........ ··.··p14.2(256) 14.2 Algebraic Computation Trees ......p14.4(258) 14.3 The Blum-Shub-Smale Model ···············p14.8(262) Web draft2007-01-0821:59

DRAFT x CONTENTS 12 Communication Complexity p12.1 (221) 12.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.1 (221) 12.2 Lowerbound methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.2 (222) 12.2.1 Fooling set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.2 (222) 12.2.2 The tiling lowerbound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.3 (223) 12.2.3 Rank lowerbound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.4 (224) 12.2.4 Discrepancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.5 (225) A technique for upperbounding the discrepancy . . . . . . . . . . . . . . . . . p12.6 (226) 12.2.5 Comparison of the lowerbound methods . . . . . . . . . . . . . . . . . . . . . p12.7 (227) 12.3 Multiparty communication complexity . . . . . . . . . . . . . . . . . . . . . . . . . . p12.8 (228) Discrepancy-based lowerbound . . . . . . . . . . . . . . . . . . . . . . . . . . p12.9 (229) 12.4 Probabilistic Communication Complexity . . . . . . . . . . . . . . . . . . . . . . . . p12.10 (230) 12.5 Overview of other communication models . . . . . . . . . . . . . . . . . . . . . . . . p12.10 (230) 12.6 Applications of communication complexity . . . . . . . . . . . . . . . . . . . . . . . . p12.11 (231) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.11 (231) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p12.12 (232) 13 Circuit lowerbounds p13.1 (235) 13.1 AC0 and H˚astad’s Switching Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.1 (235) 13.1.1 The switching lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.2 (236) 13.1.2 Proof of the switching lemma (Lemma 13.2) . . . . . . . . . . . . . . . . . . . p13.3 (237) 13.2 Circuits With “Counters”:ACC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.5 (239) 13.3 Lowerbounds for monotone circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.8 (242) 13.3.1 Proving Theorem 13.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.8 (242) Clique Indicators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.8 (242) Approximation by clique indicators. . . . . . . . . . . . . . . . . . . . . . . . p13.9 (243) 13.4 Circuit complexity: The frontier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.11 (245) 13.4.1 Circuit lowerbounds using diagonalization . . . . . . . . . . . . . . . . . . . . p13.11 (245) 13.4.2 Status of ACC versus P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.12 (246) 13.4.3 Linear Circuits With Logarithmic Depth . . . . . . . . . . . . . . . . . . . . . p13.13 (247) 13.4.4 Branching Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.13 (247) 13.5 Approaches using communication complexity . . . . . . . . . . . . . . . . . . . . . . p13.14 (248) 13.5.1 Connection to ACC0 Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.14 (248) 13.5.2 Connection to Linear Size Logarithmic Depth Circuits . . . . . . . . . . . . . p13.15 (249) 13.5.3 Connection to branching programs . . . . . . . . . . . . . . . . . . . . . . . . p13.15 (249) 13.5.4 Karchmer-Wigderson communication games and depth lowerbounds . . . . . p13.15 (249) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.17 (251) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p13.18 (252) 14 Algebraic computation models p14.1 (255) 14.1 Algebraic circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p14.2 (256) 14.2 Algebraic Computation Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p14.4 (258) 14.3 The Blum-Shub-Smale Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p14.8 (262) Web draft 2007-01-08 21:59

CONTENTS xi l4.3.1 Complexity Classes over the Complex Numbers...··.····. .··.p14.9(263) l4.3.2 Hilbert's Nullstellensatz......··.....·.··············· p14.10(264) 14.3.3 Decidability Questions:Mandelbrot Set............... p14.10(264) Exercises································· p14.11(265) Chapter notes and history.································· .p14.11(265) III Advanced topics p14.13(267) 15 Average Case Complexity:Levin's Theory p15.1(269) 15.1 Distributional Problems.. ·····p15.2(270) 15.1.1 Formalizations of "real-life distributions." ·····p15.3(271) l5.2 DistNP and its complete problems.......··.··.······· p15.4(272) 15.2.1 Polynomial-Time on Average p15.4(272) 15.2.2 Reductions...........·..······.······ p15.5(273) 15.2.3 Proofs using the simpler definitions................ p15.8(276) 15.3 Existence of Complete Problems p15.10(278) 15.4 Polynomial-Time Samplability p15.10(278) Exercises··· p15.11(279) Chapter notes and history...... p15.11(279) 16 Derandomization,Expanders and Extractors p16.1(281) 16.1 Pseudorandom Generators and Derandomization p16.3(283) 16.1.1 Hardness and Derandomization.......... p16.5(285) 16.2 Proof of Theorem 16.10:Nisan-Wigderson Construction p16.7(287) l6.2.1 WVarmup:two toy examples···· p16.8(288) Extending the input by one bit using Yao's Theorem. p16.8(288) Extending the input by two bits using the averaging principle. p16.9(289) Beyond two bits:.·.····················· p16.10(290) l6.2.2 The NW Construction....·.···· p16.10(290) Conditions on the set systems and function.... .p16.11(291) Putting it all together:Proof of Theorem 16.10 from Lemmas 16.18 and 16.19p16.12(292) Construction of combinatorial designs.......................p16.13(293) 16.3 Derandomization requires circuit lowerbounds.. p16.13(293) 16.4 Explicit construction of expander graphs... p16.16(296) 16.4.1 Rotation maps....... p16.17(297) 16.4.2 The matrix/path product p16.17(297) l6.4.3 The tensor product.··.···· p16.18(298) 16.4.4 The replacement product 4 .p16.19(299 16.4.5 The actual construction....... .p16.21(301) 16.5 Deterministic logspace algorithm for undirected connectivity. p16.22(302) l6.6 Weak Random Sources and Extractors..·..·..······.··.. ..p16.25(305) l66.1 Min Entropy······················· p16.25(305) l6.6.2 Statistical.distance and Extractors··················· p16.26(306) Web draft2007-01-0821:59

DRAFT CONTENTS xi 14.3.1 Complexity Classes over the Complex Numbers . . . . . . . . . . . . . . . . . p14.9 (263) 14.3.2 Hilbert’s Nullstellensatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p14.10 (264) 14.3.3 Decidability Questions: Mandelbrot Set . . . . . . . . . . . . . . . . . . . . . p14.10 (264) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p14.11 (265) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p14.11 (265) III Advanced topics p14.13 (267) 15 Average Case Complexity: Levin’s Theory p15.1 (269) 15.1 Distributional Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.2 (270) 15.1.1 Formalizations of “real-life distributions.” . . . . . . . . . . . . . . . . . . . . p15.3 (271) 15.2 DistNP and its complete problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.4 (272) 15.2.1 Polynomial-Time on Average . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.4 (272) 15.2.2 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.5 (273) 15.2.3 Proofs using the simpler definitions . . . . . . . . . . . . . . . . . . . . . . . . p15.8 (276) 15.3 Existence of Complete Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.10 (278) 15.4 Polynomial-Time Samplability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.10 (278) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.11 (279) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p15.11 (279) 16 Derandomization, Expanders and Extractors p16.1 (281) 16.1 Pseudorandom Generators and Derandomization . . . . . . . . . . . . . . . . . . . . p16.3 (283) 16.1.1 Hardness and Derandomization . . . . . . . . . . . . . . . . . . . . . . . . . . p16.5 (285) 16.2 Proof of Theorem 16.10: Nisan-Wigderson Construction . . . . . . . . . . . . . . . . p16.7 (287) 16.2.1 Warmup: two toy examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.8 (288) Extending the input by one bit using Yao’s Theorem. . . . . . . . . . . . . . p16.8 (288) Extending the input by two bits using the averaging principle. . . . . . . . . p16.9 (289) Beyond two bits: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.10 (290) 16.2.2 The NW Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.10 (290) Conditions on the set systems and function. . . . . . . . . . . . . . . . . . . . p16.11 (291) Putting it all together: Proof of Theorem 16.10 from Lemmas 16.18 and 16.19p16.12 (292) Construction of combinatorial designs. . . . . . . . . . . . . . . . . . . . . . . p16.13 (293) 16.3 Derandomization requires circuit lowerbounds . . . . . . . . . . . . . . . . . . . . . . p16.13 (293) 16.4 Explicit construction of expander graphs . . . . . . . . . . . . . . . . . . . . . . . . . p16.16 (296) 16.4.1 Rotation maps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.17 (297) 16.4.2 The matrix/path product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.17 (297) 16.4.3 The tensor product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.18 (298) 16.4.4 The replacement product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.19 (299) 16.4.5 The actual construction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.21 (301) 16.5 Deterministic logspace algorithm for undirected connectivity. . . . . . . . . . . . . . p16.22 (302) 16.6 Weak Random Sources and Extractors . . . . . . . . . . . . . . . . . . . . . . . . . . p16.25 (305) 16.6.1 Min Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.25 (305) 16.6.2 Statistical distance and Extractors . . . . . . . . . . . . . . . . . . . . . . . . p16.26 (306) Web draft 2007-01-08 21:59