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