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

Leibniz international proceedings in informatics

Lower Bounds for the Approximate Degree of Block-Composed Functions

Justin Thaler

Published Jan 1, 2016• 15 citations
Publisher

Abstract

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).

DOI
10.4230/lipics.icalp.2016.17

Related papers

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.

•Jan 1, 2022•0 citations

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.

cs.CCCross-listedarXiv:2609.30139•Sep 25, 2026•0 citations

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This monograph surveys what is known about approximate degree and illustrates its applications in theoretical computer science. A particular focus of the survey is a method of proving lower bounds via objects called dual polynomials. These represent a reformulation of approximate degree using linear programming duality. We discuss in detail a recent, powerful technique for constructing dual polynomials, called “dual block composition”.

Foundations and Trends® in Theoretical Computer Science•Dec 30, 2022•2 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.

SIAM Journal on Computing•Jun 10, 2025•1 citation

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•0 citations

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Mark Bun, Justin Thaler

The $ε$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $ε$ in the $\ell_\infty$ 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 $Θ(\sqrt{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.

arXiv:1302.6191•Feb 25, 2013•1 citation
We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).
The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.
A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} and g:{0,1}m→{0,1}g:\{0,1\}^m\to\{0,1\}g:{0,1}m→{0,1}, deg~(f∘g)=Θ ⁣(deg~(f) deg~(g)), \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), deg​(f∘g)=Θ(deg​(f)deg​(g)), where deg~\widetilde{deg}deg​ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.
The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This monograph surveys what is known about approximate degree and illustrates its applications in theoretical computer science. A particular focus of the survey is a method of proving lower bounds via objects called dual polynomials. These represent a reformulation of approximate degree using linear programming duality. We discuss in detail a recent, powerful technique for constructing dual polynomials, called “dual block composition”.
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.
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}f: \{-1, 1\}^n \to \{-1, 1\}f:{−1,1}n→{−1,1} is the minimum degree of a real polynomial that approximates fff to within εεε in the ℓ∞\ell_\inftyℓ∞​ 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ε> 0ε>0. We show that this quantity is Θ(n)Θ(\sqrt{n})Θ(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.