Abstract
We show that AC^0 circuits on n variables with depth d and size m have at most 2^{Omega(k/log^{d1} m)} 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 Omega notation.
As an application, we improve Braverman's celebrated result (JACM, 2010). Braverman showed that any r(m,d,epsilon)wise independent distribution epsilonfools 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's paper  Algorithmica, 1996) shows that there is a log^{d1}(m)\log(1/epsilon)wise independent distribution that does not epsilonfool AC^0 circuits of size m and depth d. Hence, our result is tight up to the factor $3$ in the exponent.
BibTeX  Entry
@InProceedings{tal:LIPIcs:2017:7525,
author = {Avishay Tal},
title = {{Tight Bounds on the Fourier Spectrum of AC0}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {15:115:31},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7525},
URN = {urn:nbn:de:0030drops75258},
doi = {10.4230/LIPIcs.CCC.2017.15},
annote = {Keywords: bounded depth circuits, Fourier analysis, kwise independence, Boolean circuits, switching lemma}
}
Keywords: 

bounded depth circuits, Fourier analysis, kwise independence, Boolean circuits, switching lemma 
Seminar: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

21.07.2017 