Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Annual Symposium on Foundations of Computer Science

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

Mark Bun, Justin Thaler

Published Oct 1, 2017• 26 citations
Publisher

Abstract

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.

DOI
10.1109/focs.2017.10

Related papers

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

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-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 \cdot \mathrm{polylog}(n))$ variables with approximate degree at least $D = \Omega(n^{1/3} \cdot 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$.

arXiv:1703.05784•SIAM Journal on Computing•Oct 22, 2019•18 citations

The Large-Error Approximate Degree of AC^0

Mark Bun, Justin Thaler

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.

Leibniz international proceedings in informatics•Jan 1, 2019•3 citations

The approximate degree of DNF and CNF formulas

Alexander A. Sherstov

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 any δ>0, we construct DNF and CNF formulas of polynomial size with approximate degree Ω(n1−δ), essentially matching the trivial upper bound of n. This fully resolves the approximate degree of constant-depth circuits (AC0), a question that has seen extensive research over the past 10 years. Prior to our work, an Ω(n1−δ) lower bound was known only for AC0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Furthermore, the DNF and CNF formulas that we construct are the simplest possible in that they have constant width.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•3 citations

The Approximate Degree of DNF and CNF Formulas

Alexander A. Sherstov

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.

arXiv:2209.01584•SIAM Journal on Computing•Jun 10, 2025•3 citations

Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ 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 novel, first-principles 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(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})$ for the $k$-element distinctness problem; $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; and $O(n^{3/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 $\Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $\Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

arXiv:1801.04607•SIAM Journal on Computing•Jan 1, 2020•10 citations

The polynomial method strikes back: tight quantum query bounds via dual polynomials

Mark Bun, Robin Kothari, Justin Thaler

The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001).

arXiv:1710.09079•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2018•58 citations
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^00
The approximate degree of a Boolean function f ⁣:{−1,1}n→{−1,1}f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates fff 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 fff with approximate degree ddd into a function FFF on O(n⋅polylog(n))O(n \cdot \mathrm{polylog}(n))O(n⋅polylog(n)) variables with approximate degree at least D=Ω(n1/3⋅d2/3)D = \Omega(n^{1/3} \cdot d^{2/3})D=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(1)d= n^{1-\Omega(1)}d=n1−Ω(1), then DDD is polynomially larger than ddd. Moreover, if fff is computed by a polynomial-size Boolean circuit of constant depth, then so is FFF. By recursively applying our transformation, for any constant δ>0\delta > 0δ>0 we exhibit an AC0^00 function of approximate degree Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ). This improves upon the best previous lower bound of Ω(n2/3)\Omega(n^{2/3})Ω(n2/3) due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of nnn 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\delta > 0δ>0, an Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0^00; (ii) a Boolean function fff with approximate degree at least C(f)2−o(1)C(f)^{2-o(1)}C(f)2−o(1), where C(f)C(f)C(f) is the certificate complexity of fff; this separation is optimal up to the o(1)o(1)o(1) term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC0^00.
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∶{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 any δ>0, we construct DNF and CNF formulas of polynomial size with approximate degree Ω(n1−δ), essentially matching the trivial upper bound of n. This fully resolves the approximate degree of constant-depth circuits (AC0), a question that has seen extensive research over the past 10 years. Prior to our work, an Ω(n1−δ) lower bound was known only for AC0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Furthermore, the DNF and CNF formulas that we construct are the simplest possible in that they have constant width.
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(x1,x2,…,xn)f(x_{1},x_{2},\ldots,x_{n})f(x1​,x2​,…,xn​) is the minimum degree of a real polynomial that approximates fff pointwise within 1/31/31/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 novel, first-principles 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(n34−14(2k−1))O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})O(n43​−4(2k−1)1​) for the kkk-element distinctness problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for the kkk-subset sum problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for any kkk-DNF or kkk-CNF formula; and O(n3/4)O(n^{3/4})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)\Theta(n)Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n)\Omega(n)Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.