ECCC-Report TR16-068https://eccc.weizmann.ac.il/report/2016/068Comments and Revisions published for TR16-068en-usThu, 28 Apr 2016 15:00:51 +0300
Revision 1
| On Polynomial Approximations to $\mathrm{AC}^0$ |
Prahladh Harsha,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2016/068#revision1We 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).
Thu, 28 Apr 2016 15:00:51 +0300https://eccc.weizmann.ac.il/report/2016/068#revision1
Paper TR16-068
| On Polynomial Approximations to $\mathrm{AC}^0$ |
Prahladh Harsha,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2016/068We 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).
Thu, 28 Apr 2016 13:50:43 +0300https://eccc.weizmann.ac.il/report/2016/068