# Random Structures & Algorithms

## On polynomial approximations to AC ${}^{0}$

### Abstract

Classical ${\text{AC}}^{0}$ approximation results show that any ${\text{AC}}^{0}$ circuit of size $s$ and depth $d$ has an $\varepsilon$ ‐error probabilistic polynomial over the reals of degree ${\left(\mathrm{log}\left(s/\varepsilon \right)\right)}^{O\left(d\right)}$. We improve this upper bound to ${\left(\mathrm{log}s\right)}^{O\left(d\right)}·\mathrm{log}\left(1/\varepsilon \right)$, which is much better for small values of $\varepsilon$. We then use this result to show that ${\left(\mathrm{log}s\right)}^{O\left(d\right)}·\mathrm{log}\left(1/\varepsilon \right)$ ‐wise independence fools ${\text{AC}}^{0}$ circuits of size $s$ and depth $d$ up to error at most $\varepsilon$, improving on Tal's strengthening of Braverman's result that ${\left(\mathrm{log}\left(s/\varepsilon \right)\right)}^{O\left(d\right)}$ ‐wise independence suffices. To our knowledge, this is the first PRG construction for ${\text{AC}}^{0}$ that achieves optimal dependence on the error $\varepsilon$. We also prove lower bounds on the best polynomial approximations to ${\text{AC}}^{0}$. We show that any polynomial approximating the $\text{OR}$ function on $n$ bits to a small constant error must have degree at least $\stackrel{\sim }{\mathrm{\Omega }}\left(\sqrt{\mathrm{log}n}\right)$. This result improves exponentially on a result of Meka, Nguyen, and Vu (Theory Comput. 2016).

View all

View all