Open Collections

A Nearly Optimal Lower Bound on the Approximate Degree of $AC^0$

Banff International Research Station for Mathematical Innovation and Discovery

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. I will also describe a number of applications of this result to communication complexity and cryptography. This is joint work with Mark Bun.

Mathematics; Computer science; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: Georgetown University

2017-09-17

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/63058

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/