We give an explicit pseudorandom generator (PRG) for read-once AC 0 , i.e., constant-depth read-once formulas over the basis with unbounded fan-in. The seed length of our PRG is O ( log ( n )) . Previously, PRGs with near-optimal seed length were known only for the depth- 2 case [GMRTV12]. For a constant depth 2"> d 2 , the best prior PRG is a recent construction by Forbes and Kelley with seed length O ( log 2 n + log n log (1 )) for the more general model of constant-width read-once branching programs with arbitrary variable order [FK18]. Looking beyond read-once AC 0 , we also show that our PRG fools read-once AC 0 [ ] with seed length O ( t + log ( n )) , 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 AC 0 formulas. To fool depth- ( d + 1 ) 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 pol y ( log log n ) independent applications of our pseudorandom restriction, the formula simplifies in the sense that every gate other than the output has only polylo g n remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal [MRT18] to fool this simpler formula.