Opening Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
- Length
- 12 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Hardness versus randomness paradigm
The hardness versus randomness paradigm builds pseudorandom generators from worst-case hard Boolean functions, evaluated on subsets of a short seed. O'Donnell states the Impagliazzo-Wigderson theorem: if a problem such as SAT requires exponential-size circuits, then . Student questions probe the worst-case hardness assumption and its relation to exponential-time hypotheses. The second part turns to Nisan's 1992 generator, which fools space-bounded Turing machines with no hardness assumption and uses a polylogarithmic seed for log-space machines. That seed length gives quasi-polynomial-time derandomization of randomized log-space algorithms. Short and survey-level, the lecture forms Lecture 12b of O'Donnell's graduate CS Theory Toolkit course at Carnegie Mellon and assumes randomized complexity classes and Boolean circuits.

Your comment is kept while you sign up.Sign in
Pairs the Impagliazzo-Wigderson route from circuit lower bounds to BPP = P with Nisan's unconditional space generator.
The hardness versus randomness paradigm builds pseudorandom generators from worst-case hard Boolean functions, evaluated on subsets of a short seed. O'Donnell states the Impagliazzo-Wigderson theorem: if a problem such as SAT requires exponential-size circuits, then . Student questions probe the worst-case hardness assumption and its relation to exponential-time hypotheses. The second part turns to Nisan's 1992 generator, which fools space-bounded Turing machines with no hardness assumption and uses a polylogarithmic seed for log-space machines. That seed length gives quasi-polynomial-time derandomization of randomized log-space algorithms. Short and survey-level, the lecture forms Lecture 12b of O'Donnell's graduate CS Theory Toolkit course at Carnegie Mellon and assumes randomized complexity classes and Boolean circuits.
CS880 lecture notes "Pseudorandomness -> Derandomization"
Pseudorandomness
This lecture
Lecture 36 of 89 of A Theorist's Toolkit.
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.