Log-Seed Pseudorandom Generators via Iterated Restrictions

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The "iterated restrictions" approach, pioneered by Ajtai and Wigderson (Advances in Computing Research '89), has provided PRGs with seed length $\text{polylog } n$ or even $\widetilde{O}(\log n)$ for several restricted models of computation. Can this approach ever achieve the optimal seed length of $O(\log n)$?

In this work, we answer this question in the affirmative. Using the iterated restrictions approach, we construct an explicit PRG for read-once depth-2 $\mathbf{AC}^0[\oplus]$ formulas with seed length $$ O(\log n) + \widetilde{O}(\log(1/\varepsilon)). $$ In particular, our PRG achieves optimal seed length $O(\log n)$ with near-optimal error $\varepsilon = \exp(-\widetilde{\Omega}(\log n))$. Even for constant error, the best prior PRG for this model (which includes read-once CNFs and read-once $\mathbb{F}_2$-polynomials) has seed length $\Theta(\log n \cdot (\log \log n)^2)$ (Lee, CCC '19).

A key step in the analysis of our PRG is a tail bound for subset-wise symmetric polynomials, a generalization of elementary symmetric polynomials. Like elementary symmetric polynomials, subset-wise symmetric polynomials provide a way to organize the expansion of $\prod_{i = 1}^m (1 + y_i)$. Elementary symmetric polynomials simply organize the terms by degree, i.e., they keep track of the number of variables participating in each monomial. Subset-wise symmetric polynomials keep track of more data: for a fixed partition of $[m]$, they keep track of the number of variables from each subset participating in each monomial. Our tail bound extends prior work by Gopalan and Yehudayoff (arXiv 2014) on elementary symmetric polynomials.

A "pseudorandom generator" is an algorithm that makes a few coin tosses and outputs a long sequence of bits $(x_1, x_2, x_3, \dots)$ that "look random" in some sense. In this paper, we present a pseudorandom generator whose output looks random in the following sense. Consider a polynomial such as $$ y = x_1 x_3 + x_2 x_7 x_8 + x_4 x_5 + \dots $$ Each variable is only allowed to appear one time (it's "read-once"). The arithmetic is mod 2 (+ is really XOR, and $y$ is either 0 or 1). For every polynomial $y$ of that form, the expected value of $y$ when you plug in the output of our pseudorandom generator is approximately the same (say, to within plus or minus 0.01) as it is when you plug in truly random bits. For a fixed error value like 0.01, our pseudorandom generator is optimal, i.e., it makes essentially the smallest possible number of coin tosses.