ECCC-Report TR18-143https://eccc.weizmann.ac.il/report/2018/143Comments and Revisions published for TR18-143en-usSat, 18 Aug 2018 11:13:43 +0300
Paper TR18-143
| The Large-Error Approximate Degree of AC$^0$ |
Mark Bun,
Justin Thaler
https://eccc.weizmann.ac.il/report/2018/143We 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 2015). 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 2016).
Second, for any $\delta>0$, we exhibit a function $f \colon \{-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 $\varepsilon=1-2^{-\Omega(n^{1-\delta})}$, even by polynomials of degree $n^{1-\delta}$. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error $\varepsilon=1/3$.
Our result implies $2^{\Omega(n^{1-\delta})}$ 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^{\Omega(n^{1/2})}$ (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.Sat, 18 Aug 2018 11:13:43 +0300https://eccc.weizmann.ac.il/report/2018/143