Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MARGIN COMPLEXITY:
Reports tagged with margin complexity:
TR18-143 | 16th August 2018
Mark Bun, Justin Thaler

#### The Large-Error Approximate Degree of AC$^0$

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$ ... more >>>

ISSN 1433-8092 | Imprint