pdf icon
Volume 17 (2021) Article 7 pp. 1-46
APPROX-RANDOM 2019 Special Issue
The Large-Error Approximate Degree of AC$^0$
Received: January 24, 2020
Revised: August 18, 2020
Published: September 23, 2021
Download article from ToC site:
[PDF (486K)] [PS (2976K)] [Source ZIP]
Keywords: approximate degree, polynomial approximation, polynomial threshold, polynomial method, dual polynomials, surjectivity, discrepancy
ACM Classification: F.1.2, F.1.3
AMS Classification: 68Q15, 68Q17, 68Q32

Abstract: [Plain Text Version]

$ \newcommand{\bits}{\{-1,1\}} \newcommand{\eps}{\varepsilon} $

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the $\mathsf{SURJECTIVITY}$ function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS'15). Our result also extends to a $2^{\tilde{\Omega}(n^{1/2})}$ lower bound on the sign-rank of an AC$^0$ function, improving on the previous best bound of $2^{\Omega(n^{2/5})}$ (Bun and Thaler, ICALP'16). Second, for any $\delta> 0$, we exhibit a function $f \colon \bits^n \to \bits$ that is computed by a circuit of depth $O(1/\delta)$ and is hard to approximate by polynomials in the following sense: $f$ cannot be uniformly approximated to error $\eps=1-2^{-\Omega(n^{1-\delta})}$, even by polynomials of degree $n^{1-\delta}$. In our FOCS'17 paper we proved a similar lower bound, but which held only for error $\eps=1/3$. Our result implies $2^{\Omega(n^{1-\delta})}$ lower bounds on the complexity of AC$^0$ under a variety of measures, including discrepancy, margin complexity, and threshold weight, that are central to communication complexity and learning theory. This nearly matches the trivial upper bound of $2^{O(n)}$ that holds for every function. The previous best lower bound on AC$^0$ for these measures was $2^{\Omega(n^{1/2})}$ (Sherstov, FOCS'15). Additional applications in learning theory, communication complexity, and cryptography are described.