Theory of Computing
-------------------
Title     : The Large-Error Approximate Degree of AC$^0$
Authors   : Mark Bun and Justin Thaler
Volume    : 17
Number    : 7
Pages     : 1-46
URL       : https://theoryofcomputing.org/articles/v017a007

Abstract
--------

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
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 : {-1,1}^n \to {-1,1}$ 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.