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 ( 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 2015). Our result also extends to a 2 ( n 1 2 ) lower bound on the sign-rank of an AC 0 function, improving on the previous best bound of 2 ( n 2 5 ) (Bun and Thaler, ICALP 2016). Second, for any 0" 0 , we exhibit a function f : ? 1 1 n ? 1 1 that is computed by a circuit of depth O (1 ) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error = 1 ? 2 ? ( n 1 ? ) , even by polynomials of degree n 1 ? . Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error = 1 3 .Our result implies 2 ( n 1 ? ) lower bounds on the complexity of AC 0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. 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 ( n 1 2 ) (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.
展开▼
