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