TR19-149 Authors: Dean Doron, Pooya Hatami, William Hoza

Publication: 4th November 2019 15:16

Downloads: 1001

Keywords:

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The ``iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length $\mathrm{polylog} n$ or even $\tilde{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) + \tilde{O}(\log(1/\epsilon))$. In particular, our PRG achieves optimal seed length $O(\log n)$ with near-optimal error $\epsilon = \exp(-\tilde{\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)$ [Lee19].

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 [GY14] on elementary symmetric polynomials.