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

 Computer Science/Discrete Mathematics Seminar I Topic: A nearly optimal lower bound on the approximate degree of AC$^0$ Speaker: Mark Bun Affiliation: Princeton University Date: Monday, October 23 Time/Room: 11:00am - 12:15pm/S-101 Video Link: https://video.ias.edu/csdm/2017/1023-MarkBun

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