ECCC-Report TR14-174https://eccc.weizmann.ac.il/report/2014/174Comments and Revisions published for TR14-174en-usMon, 09 Jan 2017 23:14:15 +0200
Revision 2
| Tight bounds on The Fourier Spectrum of $AC^0$ |
Avishay Tal
https://eccc.weizmann.ac.il/report/2014/174#revision2We 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.Mon, 09 Jan 2017 23:14:15 +0200https://eccc.weizmann.ac.il/report/2014/174#revision2
Revision 1
| Tight bounds on The Fourier Spectrum of $AC^0$ |
Avishay Tal
https://eccc.weizmann.ac.il/report/2014/174#revision1We 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.Thu, 07 May 2015 16:30:33 +0300https://eccc.weizmann.ac.il/report/2014/174#revision1
Paper TR14-174
| Tight bounds on The Fourier Spectrum of $AC^0$ |
Avishay Tal
https://eccc.weizmann.ac.il/report/2014/174We 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.Sun, 14 Dec 2014 21:56:46 +0200https://eccc.weizmann.ac.il/report/2014/174