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