Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR18-183 | 20th February 2019 20:35

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

RSS-Feed




Revision #2
Authors: Dean Doron, Pooya Hatami, William Hoza
Accepted on: 20th February 2019 20:35
Downloads: 639
Keywords: 


Abstract:

We give an explicit pseudorandom generator (PRG) for read-once $\mathbf{AC}^0$, i.e., constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\tilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-$2$ case [GMRTV12]. For a constant depth $d > 2$, the best prior PRG is a recent construction by Forbes and Kelley with seed length $\tilde{O}(\log^2 n + \log n \log(1/\varepsilon))$ for the more general model of constant-width read-once branching programs with arbitrary variable order [FK18].
Looking beyond read-once $\mathbf{AC}^0$, we also show that our PRG fools read-once $\mathbf{AC}^0[\oplus]$ with seed length $\tilde{O}(t + \log(n/\varepsilon))$, where $t$ is the number of parity gates in the formula.

Our construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions [AW89]. We assume by recursion that we already have a PRG for depth-$d$ $\mathbf{AC}^0$ formulas. To fool depth-$(d + 1)$ $\mathbf{AC}^0$ formulas, we use the given PRG, combined with a small-bias distribution and almost $k$-wise independence, to sample a pseudorandom restriction. The analysis of Forbes and Kelley [FK18] shows that our restriction approximately preserves the expectation of the formula. The crux of our work is showing that after $\mathrm{poly}(\log \log n)$ independent applications of our pseudorandom restriction, the formula simplifies in the sense that every gate other than the output has only $\mathrm{polylog} n$ remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal [MRT18] to fool this simpler formula.



Changes to previous version:

Handling parity gates.


Revision #1 to TR18-183 | 9th November 2018 20:10

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas





Revision #1
Authors: Dean Doron, Pooya Hatami, William Hoza
Accepted on: 9th November 2018 20:10
Downloads: 560
Keywords: 


Abstract:

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth $d > 2$, the best prior PRG is a recent construction by Forbes and Kelley with seed length $\widetilde{O}(\log^2 n + \log n \log(1/\varepsilon))$ for the more general model of constant-width read-once branching programs with arbitrary variable order (FOCS '18). Our result improves on the Forbes-Kelley PRG even when $d$ is slightly super-constant.

Our construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions (Advances in Computing Research '89). We assume by recursion that we already have a PRG for depth-$d$ formulas. To fool depth-$(d + 1)$ formulas, we use the given PRG, combined with a small-bias distribution and almost $k$-wise independence, to sample a pseudorandom restriction. The analysis of Forbes and Kelley shows that our restriction approximately preserves the expectation of the formula. The crux of our work is showing that after $\mathrm{poly}(\log \log n)$ independent applications of our pseudorandom restriction, the formula simplifies in the sense that every gate other than the output has only $\mathrm{polylog}n$ remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal (arXiv '18) to fool this simpler formula.



Changes to previous version:

Minor revisions in the introduction section.


Paper:

TR18-183 | 5th November 2018 19:00

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas





TR18-183
Authors: Dean Doron, Pooya Hatami, William Hoza
Publication: 5th November 2018 19:22
Downloads: 691
Keywords: 


Abstract:

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth $d > 2$, the best prior PRG is a recent construction by Forbes and Kelley with seed length $\widetilde{O}(\log^2 n + \log n \log(1/\varepsilon))$ for the more general model of constant-width read-once branching programs with arbitrary variable order (FOCS '18). Our result improves on the Forbes-Kelley PRG even when $d$ is slightly super-constant.

Our construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions (Advances in Computing Research '89). We assume by recursion that we already have a PRG for depth-$d$ formulas. To fool depth-$(d + 1)$ formulas, we use the given PRG, combined with a small-bias distribution and almost $k$-wise independence, to sample a pseudorandom restriction. The analysis of Forbes and Kelley shows that our restriction approximately preserves the expectation of the formula. The crux of our work is showing that after $\mathrm{poly}(\log \log n)$ independent applications of our pseudorandom restriction, the formula simplifies in the sense that every gate other than the output has only $\mathrm{polylog}n$ remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal (arXiv '18) to fool this simpler formula.



ISSN 1433-8092 | Imprint