## Tight bounds on The Fourier Spectrum of AC0

by Avishay Tal

#### Oded's comments

This work relies on Johan's bound
[see ECCC TR12-137]
on the correlation of Depth $d$ circuits of size $m$
with the $n$-parity function.
(Johan's result went under the radar of this list of choices,
and I feel odd to correct this annoying omission now...)

Personally, I find the correlation of constant-depth
circuits with partity, as well as its generalization
to the mass of the tail of the Fourier spectrum,
at least as interesting as the application to PRGs
(which is highlighted in the 2nd paragraph of the abstract).

#### The original abstract

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most
$\exp(-\Omega(k/(\log m)^{d-1}))$ of their Fourier mass at level $k$ or
above. Our proof builds on a previous result by Hastad (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.

See
ECCC TR12-174.

Back to
list of Oded's choices.