2026-10-11T03:29:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7525 2024-03-06T09:40:12Z ddc:004 open_access

Tight Bounds on the Fourier Spectrum of AC0 Tal, Avishay bounded depth circuits Fourier analysis k-wise independence Boolean circuits switching lemma We show that AC^0 circuits on n variables with depth d and size m have at most 2^{-Omega(k/log^{d-1} 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 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's paper - Algorithmica, 1996) shows that there is a log^{d-1}(m)\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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avishay Tal 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.15 urn:nbn:de:0030-drops-75258 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.15 eng https://creativecommons.org/licenses/by/3.0/legalcode