We show that $AC^0$ circuits on $n$ variables with depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up to the constants hidden in the $\Omega$ notation.

As an application, we improve Braverman's celebrated result (JACM, 2010). Braverman showed that any $r(m,d,\epsilon)$-wise independent distribution $\epsilon$-fools $AC^0$ circuits of size $m$ and depth $d$, for
\[r(m,d,\epsilon) = O(\log (m/\epsilon))^{2d^2+7d+3}\;.\]
Our improved bounds on the Fourier tails of $AC^0$ circuits allows us to improve this estimate to
\[r(m,d,\epsilon) = O(\log(m/\epsilon))^{3d+3}\;.\]
In contrast, an example by Mansour (appearing in Luby and Velickovic - Algorithmica, 1996) shows that there is a $\log(m)^{d-1}\cdot \log(1/\epsilon)$-wise independent distribution that doesn't $\epsilon$-fool $AC^0$ circuits of size $m$ and depth $d$. Hence, our results are tight up to the factor $3$ in the exponent.

Added a new proof for Hastad's "switch-many" lemma.
Added sections explaining the improvements to the PRGs for DNFs by De et al. and the PRGs for AC0 circuits by Trevisan and Xue.

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result improves the seminal result of Linial, Mansour and Nisan (JACM, 1993) and is tight up to the constants hidden in the $\Omega$ notation.

As an application, we improve Braverman's celebrated result (CACM, 2011). Braverman showed that any $r(m,d,\epsilon)$-wise independent distribution $\epsilon$-fools $AC^0$ circuits of size $m$ and depth $d$, for
\[r(m,d,\epsilon) = O(\log (m/\epsilon))^{2d^2+7d+3}\;.\]
Our improved bounds on the Fourier tails of $AC^0$ circuits allows us to improve this estimate to
\[r(m,d,\epsilon) = O(\log(m/\epsilon))^{3d+3}\;.\]
In contrast, an example by Mansour (appearing in Luby and Velickovic - Algorithmica, 1996) shows that there is a $\log(m)^{d-1}\cdot \log(1/\epsilon)$-wise independent distribution that does not $\epsilon$-fool $AC^0$ circuits of size $m$ and depth $d$. Hence, our result is tight up to the factor $3$ in the exponent.

In this revision, we fix several typos, introduce the definition of restriction trees and a reference to a paper of Shaltiel and Viola, and add acknowledgements.

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up to the constants hidden in the $\Omega$ notation.

As an application, we improve Braverman's celebrated result (CACM, 2011). Braverman showed that any $r(m,d,\epsilon)$-wise independent distribution $\epsilon$-fools $AC^0$ circuits of size $m$ and depth $d$, for
\[r(m,d,\epsilon) = O(\log (m/\epsilon))^{2d^2+7d+3}\;.\]
Our improved bounds on the Fourier tails of $AC^0$ circuits allows us to improve this estimate to
\[r(m,d,\epsilon) = O(\log(m/\epsilon))^{3d+3}\;.\]
In contrast, an example by Mansour (appearing in Luby and Velickovic - Algorithmica, 1996) shows that there is a $\log(m)^{d-1}\cdot \log(1/\epsilon)$-wise independent distribution that doesn't $\epsilon$-fool $AC^0$ circuits of size $m$ and depth $d$. Hence, our results are tight up to the factor $3$ in the exponent.