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

Wednesday, December 12, 2018 - 4:00pm to 5:00pm
Dean Doron
UT Austin
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.