Dean Doron: Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Abstract: We give an explicit nearly-optimal pseudorandom generator (PRG) for constant-depth read-once formulas. Previously, PRGs with near-optimal seed length were known only for the depth-2 case by Gopalan et al.. For a constant depth d > 2, the best prior PRG is a recent construction by Forbes and Kelley with seed length O(log^2 n) for the more general model of constant-width read-once branching programs with arbitrary variable order.
Our construction follows Ajtai and Wigderson’s approach of iterated pseudorandom restrictions, and the main technical crux of our work is constructing a suitable pseudorandom restriction generator for constant-depth read-once formulas having a short seed.

Joint work with Pooya Hatami and William Hoza.