Opening Hardness vs. Randomness II
Hardness vs. Randomness II
- Length
- 1 h 18 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 9: Review of the hardness versus randomness plan
Proves Yao's next-bit prediction theorem via the hybrid method to construct pseudorandom generators from hard functions.
Ryan O'Donnell proves the Nisan–Wigderson theorem for derandomizing BPP in session 25 of CMU 15-855, Graduate Computational Complexity Theory. He uses a hybrid argument to turn a distinguisher into a next-bit predictor and analyzes hardness amplification via Yao's XOR lemma.
Ryan O'Donnell proves the Nisan–Wigderson theorem for derandomizing BPP in session 25 of CMU 15-855, Graduate Computational Complexity Theory. He uses a hybrid argument to turn a distinguisher into a next-bit predictor and analyzes hardness amplification via Yao's XOR lemma.
Babai, Fortnow, Nisan, Wigderson (1993)
Derandomization of Yao's XOR Lemma
This lecture
Lecture 25 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