A nearly optimal lower bound on the approximate degree of AC$^0$

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. For any constant $\delta > 0$, we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This improves over the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi, and nearly matches the trivial upper bound of $n$ that holds for any function.

Our lower bound follows from a new hardness amplification theorem, which shows how to increase the approximate degree of a given function while preserving its computability by constant-depth circuits. I will also describe several applications of our results in communication complexity and cryptography.

This is joint work with Justin Thaler and is available at https://eccc.weizmann.ac.il/report/2017/051/.