Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR14-174 | 9th January 2017 23:14

Tight bounds on The Fourier Spectrum of $AC^0$

RSS-Feed




Revision #2
Authors: Avishay Tal
Accepted on: 9th January 2017 23:14
Downloads: 1919
Keywords: 


Abstract:

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



Changes to previous version:

Added a new proof for Hastad's "switch-many" lemma.
Added sections explaining the improvements to the PRGs for DNFs by De et al. and the PRGs for AC0 circuits by Trevisan and Xue.


Revision #1 to TR14-174 | 7th May 2015 16:30

Tight bounds on The Fourier Spectrum of $AC^0$





Revision #1
Authors: Avishay Tal
Accepted on: 7th May 2015 16:30
Downloads: 2216
Keywords: 


Abstract:

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



Changes to previous version:

In this revision, we fix several typos, introduce the definition of restriction trees and a reference to a paper of Shaltiel and Viola, and add acknowledgements.


Paper:

TR14-174 | 14th December 2014 21:42

Tight bounds on The Fourier Spectrum of $AC^0$





TR14-174
Authors: Avishay Tal
Publication: 14th December 2014 21:56
Downloads: 2762
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint