On Polynomial Approximations to ${AC}^0$

We make progress on some questions related to polynomial approximations of ${\mathrm{A}\mathrm{C}}^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{A}\mathrm{C}}^0$ circuit of size $s$ and depth $d$ has an $\epsilon$-error probabilistic polynomial over the reals of degree $(\log (s\mathrm{/}\epsilon ){)}^{O(d)}$. We improve this upper bound to $(\log s{)}^{O(d)}\cdot \log (1\mathrm{/}\epsilon )$, which is much better for small values of $\epsilon$. 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)$-wiseindependencefools${\rm AC}^0$, improving on Tal’s strengthening of Braverman’s theorem (J. ACM, 2010) that $(\log (s/\varepsilon))^{O(d)}$-wiseindependencefools${\rm 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{A}\mathrm{C}}^0$ that achieves optimal dependence on the error $\epsilon$. We also prove lower bounds on the best polynomial approximations to ${\rm AC}^0$\mathrm{.}Weshowthatanypolynomialapproximatingthe${\rm OR}$functionon$n$bitstoasmallconstanterrormusthavedegreeatleast$\widetilde{\Omega}(\sqrt{\log n})$. This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).