A NEARLY OPTIMAL LOWER BOUND ON THE APPROXIMATE DEGREE OF AC0

The approximate degree of a Boolean function f: {-1, 1}(n)-> {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n.polylog(n)) variables with approximate degree at least D = Omega(n(1/)(3) . d(2/3)). In particular, if d = n (1-Omega(1)), then D is polynomially larger than d. Moreover, if f is computed by a polynomial-size Boolean circuit of constant depth, then so is F. By recursively applying our transformation, for any constant delta > 0 we exhibit an AC(0) function of approximate degree Omega(n(1)(-delta)). This improves upon the best previous lower bound of Omega(n(2/3)) due to Aaronson and Shi [J. ACM, 51 (2004), pp. 595-605] and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant delta > 0, an Omega(n(1-delta)) lower bound on the quantum communication complexity of a function in AC(0); (ii) a Boolean function f with approximate degree at least C(f)(2-o(1)), where C(f) is the certificate complexity of f; this separation is optimal up to the o(1) term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC(0).