Tight bounds on the Fourier spectrum of AC0
Avishay Tal · 2017
We show that AC0 circuits on n variables with depth d and size m have at most 2−Ω(k/logd−1m) 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 improves the seminal result of Linial, Mansour and Nisan (JACM, 1993) and is tight up to the constants hidden in the Ω notation.As an application, we improve Braverman's celebrated result (JACM, 2010). Braverman showed that any r(m, d, e)-wise independent distribution e-fools AC0 circuits of size m and depth d, forr(m, d,e) = O(log(m/e))2d2+7d+3.Our improved bounds on the Fourier tails of AC0 circuits allows us to improve this estimate to r(m, d,e) = O(log(m/e))3d+3.In contrast, an example by Mansour (appearing in Luby and Velickovic's paper - Algorithmica, 1996) shows that there is a logd−1(m)·log(1/e)-wise independent distribution that does not e-fool AC0 circuits of size m and depth d. Hence, our result is tight up to the factor 3 in the exponent.