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

A General Composition Theorem for Approximate Degree — E8 Intelligence Research

Andrew Stewart Caldin

Published Nov 13, 2026• 0 citations
Publisher

Abstract

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. Source: http://arxiv.org/abs/2609.30139v1 (arXiv:2609.30139v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

DOI
10.5281/zenodo.24186743

Related papers

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•1 citation

Composition Theorem for Randomized Query Complexity

Samruddhi Pednekar, Supartha Podder

For bounded-error randomized query complexity, we resolve the composition conjecture up to logarithmic factors. The general upper bound $R(f\circ g) = O\!\left(R(f)R(g)\log(R(f)+1)\right)$ was already known. Although Meiburg recently disproved constant-factor multiplicative composition for total Boolean functions, the conjecture allowing polylogarithmic losses remained open. We settle this question by proving that, for all (possibly partial) Boolean functions $f$ and $g$, \[ R(f\circ g) = Ω\!\left(\frac{R(f)R(g)}{\log(n+1)}\right), \] where $n$ is the input size for $f$.

arXiv:2611.08574•Nov 5, 2026•0 citations

Communication Lower Bounds Using Dual Polynomials

Alexander A. Sherstov

Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.

arXiv:0805.2135•Electronic colloquium on computational complexity•May 14, 2008•56 citations

Approximate Degree Composition for Recursive Functions

Sourav Chakraborty, Chandrima Kayal, Mittal, Rajat +2 more

Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let $h^d$ denote the standard $d$-fold composition of the base function $h$. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function $f:\{0,1\}^n\to \{0,1\}$ is a recursive function of the form $h^d$, with $h$ being any base function and $d= Ω(\log\log n)$. (II) The inner function is a recursive function of the form $h^d$, with $h$ being any constant arity base function (other than AND and OR) and $d= Ω(\log\log n)$, where $n$ is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.

arXiv:2407.08385•Leibniz international proceedings in informatics•Jan 1, 2024•3 citations

The Quantum KKL Inequality — E8 Intelligence Research

Andrew Stewart Caldin

In this paper, we resolve the quantum KKL conjecture of Montanaro and Osborne \cite{MO2010} for quantum Boolean functions on the $n$-qubit hypercube. More precisely, for every self-adjoint unitary $T$, we bound the largest $L_2$-influence from below by a constant multiple of $\mathrm{Var}(T)\log(n)/n$. The proof heavily depends on upper and lower commutator estimates on the Hilbert space. Source: http://arxiv.org/abs/2609.21900v1 (arXiv:2609.21900v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 9, 2026•0 citations

On the Composition of Randomized Query Complexity and Approximate Degree

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +3 more

For any Boolean functions f and g, the question whether $$\text {R}(f\circ g) = \tilde{\Theta }(\text {R}(f) \cdot \text {R}(g))$$ is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $$\widetilde{\text {deg}}(f\circ g) = \tilde{\Theta }(\widetilde{\text {deg}}(f)\cdot \widetilde{\text {deg}}(g))$$ . These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which $$\text {R}$$ and $$\widetilde{\text {deg}}$$ compose. A recent landmark result (Ben-David and Blais, 2020) showed that $$\text {R}(f \circ g) = \Omega (\text {noisyR}(f)\cdot \text {R}(g))$$ . This implies that composition holds iff $$\text {noisyR}(f) = \tilde{\Theta }(\text {R}(f))$$ . We show two results: On the other hand, we prove that $$ \widetilde{\text {deg}}(f\circ g) = \widetilde{\Omega }(\sqrt{\text {bs}(f)} \cdot \widetilde{\text {deg}}(g)), $$ where $$\text {bs}(f)$$ is the block sensitivity of f. This implies that $$\widetilde{\text {deg}}$$ composes when $$\widetilde{\text {deg}}(f)$$ is asymptotically equal to $$\sqrt{\text {bs}(f)}$$ . It is already known that both $$\text {R}$$ and $$\widetilde{\text {deg}}$$ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.

arXiv:2307.03900•Computational Complexity•Aug 20, 2026•10 citations
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}, [ \widetilde{deg}(f\circ g) = Θ!\left( \widetilde{deg}(f),\widetilde{deg}(g) \right), ] where deg~\widetilde{deg}deg​ denotes constant-error approximate degree. Source: http://arxiv.org/abs/2609.30139v1 (arXiv:2609.30139v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.
For bounded-error randomized query complexity, we resolve the composition conjecture up to logarithmic factors. The general upper bound R(f∘g)=O ⁣(R(f)R(g)log⁡(R(f)+1))R(f\circ g) = O\!\left(R(f)R(g)\log(R(f)+1)\right)R(f∘g)=O(R(f)R(g)log(R(f)+1)) was already known. Although Meiburg recently disproved constant-factor multiplicative composition for total Boolean functions, the conjecture allowing polylogarithmic losses remained open. We settle this question by proving that, for all (possibly partial) Boolean functions fff and ggg, R(f∘g)=Ω ⁣(R(f)R(g)log⁡(n+1)), R(f\circ g) = Ω\!\left(\frac{R(f)R(g)}{\log(n+1)}\right), R(f∘g)=Ω(log(n+1)R(f)R(g)​), where nnn is the input size for fff.
Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let hdh^dhd denote the standard ddd-fold composition of the base function hhh. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function f:{0,1}n→{0,1}f:\{0,1\}^n\to \{0,1\}f:{0,1}n→{0,1} is a recursive function of the form hdh^dhd, with hhh being any base function and d=Ω(log⁡log⁡n)d= Ω(\log\log n)d=Ω(loglogn). (II) The inner function is a recursive function of the form hdh^dhd, with hhh being any constant arity base function (other than AND and OR) and d=Ω(log⁡log⁡n)d= Ω(\log\log n)d=Ω(loglogn), where nnn is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.
In this paper, we resolve the quantum KKL conjecture of Montanaro and Osborne \cite{MO2010} for quantum Boolean functions on the nnn-qubit hypercube. More precisely, for every self-adjoint unitary TTT, we bound the largest L2L_2L2​-influence from below by a constant multiple of Var(T)log⁡(n)/n\mathrm{Var}(T)\log(n)/nVar(T)log(n)/n. The proof heavily depends on upper and lower commutator estimates on the Hilbert space. Source: http://arxiv.org/abs/2609.21900v1 (arXiv:2609.21900v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
For any Boolean functions f and g, the question whether R(f∘g)=Θ~(R(f)⋅R(g))\text {R}(f\circ g) = \tilde{\Theta }(\text {R}(f) \cdot \text {R}(g))R(f∘g)=Θ~(R(f)⋅R(g)) is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg~(f∘g)=Θ~(deg~(f)⋅deg~(g))\widetilde{\text {deg}}(f\circ g) = \tilde{\Theta }(\widetilde{\text {deg}}(f)\cdot \widetilde{\text {deg}}(g))deg​(f∘g)=Θ~(deg​(f)⋅deg​(g)) . These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R\text {R}R and deg~\widetilde{\text {deg}}deg​ compose. A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g)=Ω(noisyR(f)⋅R(g))\text {R}(f \circ g) = \Omega (\text {noisyR}(f)\cdot \text {R}(g))R(f∘g)=Ω(noisyR(f)⋅R(g)) . This implies that composition holds iff noisyR(f)=Θ~(R(f))\text {noisyR}(f) = \tilde{\Theta }(\text {R}(f))noisyR(f)=Θ~(R(f)) . We show two results: On the other hand, we prove that deg~(f∘g)=Ω~(bs(f)⋅deg~(g)), \widetilde{\text {deg}}(f\circ g) = \widetilde{\Omega }(\sqrt{\text {bs}(f)} \cdot \widetilde{\text {deg}}(g)), deg​(f∘g)=Ω(bs(f)​⋅deg​(g)), where bs(f)\text {bs}(f)bs(f) is the block sensitivity of f. This implies that deg~\widetilde{\text {deg}}deg​ composes when deg~(f)\widetilde{\text {deg}}(f)deg​(f) is asymptotically equal to bs(f)\sqrt{\text {bs}(f)}bs(f)​ . It is already known that both R\text {R}R and deg~\widetilde{\text {deg}}deg​ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.