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.