Abstract

This is a survey of unconditional pseudorandom generators (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that "fools" the model, meaning that every function computable in the model behaves approximately the same when we plug in pseudorandom bits from the PRG as it does when we plug in truly random bits. In this survey, we discuss four major paradigms for designing PRGs:

• We present several PRGs based on k-wise uniform generators, small-bias generators, and simple combinations thereof, including proofs of Viola's theorem on fooling low-degree polynomials [242] and Braverman's theorem on fooling AC⁰ circuits [36].

• We present several PRGs based on "recycling" random bits to take advantage of communication bottlenecks, such as the Impagliazzo-Nisan-Wigderson generator [131].

• We present connections between PRGs and computational hardness, including the Nisan-Wigderson framework for converting a hard Boolean function into a PRG [183].

• We present PRG frameworks based on random restrictions, including the "polarizing random walks" framework [49].

We explain how to use these paradigms to construct PRGs that work unconditionally, with no unproven complexity-theoretic assumptions. The PRG constructions use ingredients such as finite field arithmetic, expander graphs, and randomness extractors. The analyses use techniques such as Fourier analysis, sandwiching approximators, and simplification-under-restrictions lemmas.

Paradigms for Unconditional Pseudorandom Generators

In this comprehensive survey of unconditional pseudorandom generators (PRGs), the authors present the reader with an intuitive introduction to some of the most important frameworks and techniques for constructing unconditional PRGs for restricted models of computation.

The authors discuss four major paradigms for designing PRGs: several PRGs based on k-wise uniform generators, small-bias generators, and simple combinations thereof, several PRGs based on “recycling” random bits to take advantage of communication Bottlenecks, connections between PRGs and computational hardness, and PRG frameworks based on random restrictions.

The authors explain how to use these paradigms to construct PRGs that work unconditionally, with no unproven mathematical assumptions. The PRG constructions use ingredients such as finite field arithmetic, expander graphs, and randomness extractors. The analyses use techniques such as Fourier analysis, sandwiching approximators, and simplification-under-restrictions lemmas.

Paradigms for Unconditional Pseudorandom Generators offers the reader a grounding in an important topic widely used in theoretical computer science and cryptography.