We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same stretch but only fools circuits of depth $2$ with one arbitrary symmetric gate at the top. Our generator fools a strictly richer class of circuits than Nisan's generator for constant depth circuits (Combinatorica '91) (but Nisan's generator has a much bigger stretch).

In particular, we conclude that every function computable by uniform $\poly(n)$-size \emph{probabilistic} constant depth circuits with $O(\log n)$ arbitrary symmetric gates is in $\mathit{TIME}\rb{2^{n^{o(1)}} }$. This seems to be the richest probabilistic circuit class known to admit a subexponential derandomization.

Our generator is obtained by constructing an explicit function $f : \zo^n \to \zo$ that is very hard \emph{on average} for constant-depth circuits of size $n^{\eps \cdot \log n}$ with $\eps \log^2 n$ arbitrary symmetric gates, and plugging it into the Nisan-Wigderson pseudorandom generator construction (FOCS '88). The proof of the average-case hardness of this function is a modification of arguments by Razborov and Wigderson (IPL '93), and Hansen and Miltersen (MFCS '04), and combines H{\r{a}}stad's switching lemma (STOC '86) with a multiparty communication complexity lower bound by Babai, Nisan and Szegedy (STOC '89).