Opening Pseudorandom Generators
Pseudorandom Generators
- Length
- 21 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Pseudorandom generators stretch a short random seed into a long string that no test in a given class can tell apart from true randomness. O'Donnell starts by modelling a randomized algorithm as taking an input together with a separate string of coin flips. From there he defines BPP as the class of decision problems solved in polynomial time with high probability. He then states Yao and Blum's definition of an -pseudorandom generator, with a class of Boolean circuits serving as the statistical tests. The derandomization argument follows: a deterministic generator that expands a logarithmic seed to bits and fools polynomial-size circuits lets the algorithm run on every seed in polynomial time.

Your comment is kept while you sign up.Sign in
O'Donnell shows that a generator stretching a logarithmic seed to fool polynomial-size circuits would put BPP inside P.
Pseudorandom generators stretch a short random seed into a long string that no test in a given class can tell apart from true randomness. O'Donnell starts by modelling a randomized algorithm as taking an input together with a separate string of coin flips. From there he defines BPP as the class of decision problems solved in polynomial time with high probability. He then states Yao and Blum's definition of an -pseudorandom generator, with a class of Boolean circuits serving as the statistical tests. The derandomization argument follows: a deterministic generator that expands a logarithmic seed to bits and fools polynomial-size circuits lets the algorithm run on every seed in polynomial time.
Pseudorandomness
UW-Madison CS880 lecture notes
This lecture
Lecture 35 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.