A Nearly Optimal Lower Bound on the Approximate Degree of AC^0

• DOI: 10.1109/focs.2017.10
• Publication Date: 2017-11-14T13:59:34Z
• Authors: Mark Bun; Justin Thaler
• Keywords: Degree (music); Constant (computer programming); Constant function

The approximate degree of a Boolean function f : {-1, 1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> → is the least real polynomial that approximates pointwise to error at most 1/3. We introduce generic method for increasing given function, while preserving its computability by constant-depth circuits. Specifically, we show how transform any with d into F on O(n · polylog(n)) variables D = Ω(n xmlns:xlink="http://www.w3.org/1999/xlink">1/3</sup> xmlns:xlink="http://www.w3.org/1999/xlink">2/3</sup> ). In particular, if n xmlns:xlink="http://www.w3.org/1999/xlink">1-Ω(1)</sup> , then polynomially larger than d. Moreover, computed polynomial-size circuit, so F. By recursively applying our transformation, constant δ > 0 exhibit an AC xmlns:xlink="http://www.w3.org/1999/xlink">0</sup> xmlns:xlink="http://www.w3.org/1999/xlink">1-δ</sup> This improves over best previous lower bound ) due Aaronson and Shi (J. ACM 2004), nearly matches trivial upper holds function. Our bounds also apply (quasipolynomial-size) DNFs polylogarithmic width. describe several applications these results. give: For 0, quantum communication complexity in . A C(f) xmlns:xlink="http://www.w3.org/1999/xlink">2-o(1)</sup> where certificate f. separation optimal up o(1) term exponent. Improved secret sharing schemes reconstruction procedures