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

Optimal spectrum estimation — E8 Intelligence Research

Andrew Stewart Caldin

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound. Source: http://arxiv.org/abs/2609.30171v1 (arXiv:2609.30171v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 13, 2026•0 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
We prove that the spectrum of an unknown ddd-dimensional quantum state can be estimated to error ε\varepsilonε in total variation distance using O ⁣(d2min⁡{1(εlog⁡d)4,  1(εlog⁡d)2}) O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) O(d2min{(εlogd)41​,(εlogd)21​}) copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of ddd in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound. Source: http://arxiv.org/abs/2609.30171v1 (arXiv:2609.30171v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com