We prove that the OR function on {-1,1\} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous results were either not tight or had ε = Ω (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known. We prove that the \( \mathsf {OR} \) function on \( \lbrace -1,1\rbrace ^n \) can be pointwise approximated with error \( \epsilon \) by a polynomial of degree \( O(k) \) and weight \( 2^{O(n \log (1/\epsilon) /k)} \) , for any \( k \ge \sqrt {n \log (1/\epsilon)} \) . This result is tight for any \( k \le (1-\Omega (1))n \) . Previous results were either not tight or had \( \epsilon = \Omega (1) \) . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width \( \mathsf {CNF} \) . For these two classes no such result was known. One motivation for such results comes from the study of indistinguishability. Two distributions \( P \) , \( Q \) over \( n \) -bit strings are \( (k,\delta) \) -indistinguishable if their projections on any \( k \) bits have statistical distance at most \( \delta \) . The above approximations give values of \( (k,\delta) \) that suffice to fool \( \mathsf {OR} \) , symmetric functions, and bounded-width \( \mathsf {CNF} \) , and the first result is tight for all \( k \) while the second result is tight for \( k \le (1-\Omega (1))n \) . We also show that any two \( (k, \delta) \) -indistinguishable distributions are \( O(n^{k/2}\delta) \) -close to two distributions that are \( (k,0) \) -indistinguishable, improving the previous bound of \( O(n)^k \delta \) . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.
We prove that the OR function on {-1,1} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous results were either not tight or had ε = Ω (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known. We prove that the ( \mathsf {OR} ) function on ( \lbrace -1,1\rbrace ^n ) can be pointwise approximated with error ( \epsilon ) by a polynomial of degree ( O(k) ) and weight ( 2^{O(n \log (1/\epsilon) /k)} ) , for any ( k \ge \sqrt {n \log (1/\epsilon)} ) . This result is tight for any ( k \le (1-\Omega (1))n ) . Previous results were either not tight or had ( \epsilon = \Omega (1) ) . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width ( \mathsf {CNF} ) . For these two classes no such result was known. One motivation for such results comes from the study of indistinguishability. Two distributions ( P ) , ( Q ) over ( n ) -bit strings are ( (k,\delta) ) -indistinguishable if their projections on any ( k ) bits have statistical distance at most ( \delta ) . The above approximations give values of ( (k,\delta) ) that suffice to fool ( \mathsf {OR} ) , symmetric functions, and bounded-width ( \mathsf {CNF} ) , and the first result is tight for all ( k ) while the second result is tight for ( k \le (1-\Omega (1))n ) . We also show that any two ( (k, \delta) ) -indistinguishable distributions are ( O(n^{k/2}\delta) ) -close to two distributions that are ( (k,0) ) -indistinguishable, improving the previous bound of ( O(n)^k \delta ) . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.
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.
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 a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that ˜ deg(AND m ˆ OR n ) = ˜ Ω(√ mn ). We prove this lower bound via reduction to the OR function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [6, 10, 21]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson et al. [2].
Abstract. The approximate degree of a Boolean function [Formula: see text] is the minimum degree of a real polynomial [Formula: see text] that approximates [Formula: see text] pointwise: [Formula: see text] for all [Formula: see text]. For every [Formula: see text] we construct conjunctive normal form (CNF) and disjunctive normal form (DNF) formulas of polynomial size with approximate degree [Formula: see text] essentially matching the trivial upper bound of [Formula: see text]. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits [Formula: see text] a question that has seen extensive research over the past 10 years. Prior to our work, an [Formula: see text] lower bound was known only for [Formula: see text] circuits of depth that grows with [Formula: see text] (M. Bun and J. Thaler, SIAM J. Comput., 49 (2020), pp. FOCS17-59–FOCS17-96). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree. Our main result remains valid even for one-sided approximation: for any [Formula: see text], we construct a polynomial-size constant-width CNF formula with one-sided approximate degree [Formula: see text]. We thus obtain the following nearly tight separations: [Formula: see text] versus [Formula: see text] for the one-sided versus two-sided approximate degree of a function and [Formula: see text] versus [Formula: see text] for the one-sided approximate degree of a function [Formula: see text] versus its negation [Formula: see text]. As an application, we essentially settle the communication complexity of [Formula: see text] circuits in the bounded-error quantum model, [Formula: see text]-party number-on-the-forehead randomized model, and [Formula: see text]-party number-on-the-forehead nondeterministic model: we prove that for every [Formula: see text], these models require [Formula: see text], [Formula: see text], and [Formula: see text], respectively, bits of communication even for polynomial-size constant-width CNF formulas. In particular, we show that the multiparty communication class [Formula: see text] can be separated near-optimally from [Formula: see text] and [Formula: see text] by a particularly simple function, a polynomial-size constant-width CNF formula.
The ε-approximate degree of a Boolean function f:{−1,1}n→{−1,1} is the minimum degree of a real polynomial that approximates f to within ε in the ℓ∞ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the ε-approximate degree of the two-level AND-OR tree for any constant ε>0. We show that this quantity is Θ(n), closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.
The approximate degree of a Boolean function f(x1,x2,…,xn) is the minimum degree of a real polynomial that approximates f pointwise within 1/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - O(n43−4(2k−1)1) for the k-element distinctness problem; - O(n1−k+11) for the k-subset sum problem; - O(n1−k+11) for any k-DNF or k-CNF formula; - O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.