ECCC-Report TR18-183https://eccc.weizmann.ac.il/report/2018/183Comments and Revisions published for TR18-183en-usWed, 20 Feb 2019 20:35:34 +0200
Revision 2
| Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas |
Dean Doron,
William Hoza,
Pooya Hatami
https://eccc.weizmann.ac.il/report/2018/183#revision2We 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.Wed, 20 Feb 2019 20:35:34 +0200https://eccc.weizmann.ac.il/report/2018/183#revision2
Revision 1
| Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas |
Dean Doron,
William Hoza,
Pooya Hatami
https://eccc.weizmann.ac.il/report/2018/183#revision1We 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.Fri, 09 Nov 2018 20:10:57 +0200https://eccc.weizmann.ac.il/report/2018/183#revision1
Paper TR18-183
| Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas |
Dean Doron,
William Hoza,
Pooya Hatami
https://eccc.weizmann.ac.il/report/2018/183We 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.Mon, 05 Nov 2018 19:22:30 +0200https://eccc.weizmann.ac.il/report/2018/183