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 #1 to TR16-068 | 28th April 2016 15:00

On Polynomial Approximations to $\mathrm{AC}^0$

RSS-Feed

Abstract:

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals of degree $(\log (s/\varepsilon))^{O(d)}$. We improve this upper bound to $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$, which is much better for small values of $\varepsilon$.

We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$-wise independence fools $\mathrm{AC}^0$, improving on Tal's strengthening of Braverman's theorem (J. ACM 2010) that $(\log (s/\varepsilon))^{O(d)}$-wise independence fools $\mathrm{AC}^0$. Up to the constant implicit in the $O(d)$, our result is tight. As far as we know, this is the first PRG construction for $\mathrm{AC}^0$ that achieves optimal dependence on the error $\varepsilon$.

We also prove lower bounds on the best polynomial approximations to $\mathrm{AC}^0$. We show that any polynomial approximating the $\mathrm{OR}$ function on $n$ bits to a small constant error must have degree at least $\widetilde{\Omega}(\sqrt{\log n})$. This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).



Changes to previous version:

Fixed list of authors. Added keywords.


Paper:

TR16-068 | 28th April 2016 06:26

On Polynomial Approximations to $\mathrm{AC}^0$





TR16-068
Authors: Prahladh Harsha, Srikanth Srinivasan
Publication: 28th April 2016 13:50
Downloads: 598
Keywords: 


Abstract:

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals of degree $(\log (s/\varepsilon))^{O(d)}$. We improve this upper bound to $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$, which is much better for small values of $\varepsilon$.

We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$-wise independence fools $\mathrm{AC}^0$, improving on Tal's strengthening of Braverman's theorem (J. ACM 2010) that $(\log (s/\varepsilon))^{O(d)}$-wise independence fools $\mathrm{AC}^0$. Up to the constant implicit in the $O(d)$, our result is tight. As far as we know, this is the first PRG construction for $\mathrm{AC}^0$ that achieves optimal dependence on the error $\varepsilon$.

We also prove lower bounds on the best polynomial approximations to $\mathrm{AC}^0$. We show that any polynomial approximating the $\mathrm{OR}$ function on $n$ bits to a small constant error must have degree at least $\widetilde{\Omega}(\sqrt{\log n})$. This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).



ISSN 1433-8092 | Imprint