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

William Hoza
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 $\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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.