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).

Fixed list of authors. Added keywords.

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).