ECCC-Report TR19-149https://eccc.weizmann.ac.il/report/2019/149Comments and Revisions published for TR19-149en-usMon, 04 Nov 2019 15:16:42 +0200
Paper TR19-149
| Log-Seed Pseudorandom Generators via Iterated Restrictions |
Dean Doron,
William Hoza,
Pooya Hatami
https://eccc.weizmann.ac.il/report/2019/149There 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.Mon, 04 Nov 2019 15:16:42 +0200https://eccc.weizmann.ac.il/report/2019/149