Title: A Nearly Optimal Lower Bound on the Approximate Degree of AC^0
Speaker: Mark Bun, Princeton University
Date: Wednesday, April 5, 2017 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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.
We accomplish this by giving a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. We will also describe several applications to communication complexity and cryptography.
This is joint work with Justin Thaler and is available at https://eccc.weizmann.ac.il/report/2017/051/.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S17/