The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) = sgn p(x). Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. One problem that has remained open for several decades, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of a polynomial-size constant-depth circuit in n variables. The best lower bound prior to our work was Ω(n(d-1)/(2d-1)) for circuits of depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Ω(n3/7) for depth 3 and Ω(√n) for depth d ≥4. The proof contributes a novel approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.
The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) = sgn p(x). Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. One problem that has remained open for several decades, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of a polynomial-size constant-depth circuit in n variables. The best lower bound prior to our work was Ω(n(d-1)/(2d-1)) for circuits of depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Ω(n3/7) for depth 3 and Ω(√n) for depth d ≥4. The proof contributes a novel approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.
The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) ≡ sgn p(x). In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth {∧, ∨)-circuit in n variables with threshold degree Ω(n1/3). This bound underlies some of today's strongest results on constant-depth circuits. It has been an open problem (O'Donnell and Servedio, STOC 2003) to improve Minsky and Papert's bound to nΩ(1)+1/3.
The threshold degree of a Boolean function f:{0,1}n→{0,1} is the minimum degree of a real polynomial p that represents f in sign: sgnp(x)=(−1)f(x). A related notion is sign-rank, defined for a Boolean matrix F=[Fij] as the minimum rank of a real matrix M with sgnMij=(−1)Fij. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (AC0) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any ε>0, we construct an AC0 circuit in n variables that has threshold degree Ω(n1−ε) and sign-rank exp(Ω(n1−ε)), improving on the previous best lower bounds of Ω(n) and exp(Ω~(n)), respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of AC0 circuits of any given depth, with a strict improvement starting at depth 4. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of AC0, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of AC0.
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 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^{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 : {-1,1}^n -> {-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 epsilon=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 epsilon=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.
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 = Ω(n1/3· d2/3). In particular, if d = n1-Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a constant-depth polynomial-size Boolean circuit, then so is F. By recursively applying our transformation, for any constant δ > 0 we exhibit an AC0function of approximate degree Ω(n1-δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: · For any constant δ > 0, an Ω(n1-δ) lower bound on the quantum communication complexity of a function in AC0. · 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. · Improved secret sharing schemes with reconstruction procedures in AC0.
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=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(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 δ>0 we exhibit an AC0 function of approximate degree Ω(n1−δ). This improves upon the best previous lower bound of Ω(n2/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 δ>0, an Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0; (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 AC0.
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=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(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 δ>0 we exhibit an AC0 function of approximate degree Ω(n1−δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant δ>0, an Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0. * 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. * Improved secret sharing schemes with reconstruction procedures in AC0.