Opening Hardness vs. Randomness I
Hardness vs. Randomness I
- Length
- 1 h 22 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 6: Introduction to derandomization and hardness assumptions
O'Donnell builds a pseudorandom generator from an average-case hard function, proving a small-stretch warm-up first.
Derandomizing BPP under circuit lower bounds rests on the hardness-versus-randomness paradigm. O'Donnell contrasts worst-case and average-case hardness and explains how worst-case lower bounds can be amplified into average-case ones. He defines pseudorandom generators that fool circuits of a given size, then shows how a generator with logarithmic seed yields BPP = P by enumerating all seeds. After introducing notation, he builds a warm-up generator with small stretch and proves it by contradiction, using a distinguisher. Yao's next-bit prediction and combinatorial designs then extend the stretch to polynomial length. The session assumes circuit complexity and basic probability.
Derandomizing BPP under circuit lower bounds rests on the hardness-versus-randomness paradigm. O'Donnell contrasts worst-case and average-case hardness and explains how worst-case lower bounds can be amplified into average-case ones. He defines pseudorandom generators that fool circuits of a given size, then shows how a generator with logarithmic seed yields BPP = P by enumerating all seeds. After introducing notation, he builds a warm-up generator with small stretch and proves it by contradiction, using a distinguisher. Yao's next-bit prediction and combinatorial designs then extend the stretch to polynomial length. The session assumes circuit complexity and basic probability.
IW97
Hardness versus Randomness
VW97
This lecture
Lecture 24 of 27 of Graduate Computational Complexity Theory.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in
[VW94]
NW'94