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.
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.
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.
The approximate degree of a Boolean function f:{0,1}n→{0,1} is the minimum degree of a real polynomial p that approximates f pointwise: ∣f(x)−p(x)∣≤1/3 for all x∈{0,1}n. For every δ>0, we construct CNF and DNF formulas of polynomial size with approximate degree Ω(n1−δ), essentially matching the trivial upper bound of n. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits (AC0), a question that has seen extensive research over the past 10 years. Previously, an Ω(n1−δ) lower bound was known only for AC0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further consequences. (i) We essentially settle the communication complexity of AC0 circuits in the bounded-error quantum model, k-party number-on-the-forehead randomized model, and k-party number-on-the-forehead nondeterministic model: we prove that for every δ>0, these models require Ω(n1−δ), Ω(n/4kk2)1−δ, and Ω(n/4kk2)1−δ, respectively, bits of communication even for polynomial-size constant-width CNF formulas. (ii) In particular, we show that the multiparty communication class coNPk can be separated essentially optimally from NPk and BPPk by a particularly simple function, a polynomial-size constant-width CNF. (iii) We give an essentially tight separation, of O(1) versus Ω(n1−δ), for the one-sided versus two-sided approximate degree of a function; and O(1) versus Ω(n1−δ) for the one-sided approximate degree of a function f versus its negation ¬f.
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.
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems
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.
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.