Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

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

Revision #2
Authors: Avishay Tal
Accepted on: 9th January 2017 23:14
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 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
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
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