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