Revision #2 Authors: Dean Doron, Pooya Hatami, William Hoza

Accepted on: 20th February 2019 20:35

Downloads: 566

Keywords:

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.

Handling parity gates.

Revision #1 Authors: Dean Doron, Pooya Hatami, William Hoza

Accepted on: 9th November 2018 20:10

Downloads: 498

Keywords:

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.

Minor revisions in the introduction section.

TR18-183 Authors: Dean Doron, Pooya Hatami, William Hoza

Publication: 5th November 2018 19:22

Downloads: 620

Keywords:

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.