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

arXiv:2307.03900 · Computational Complexity

On the Composition of Randomized Query Complexity and Approximate Degree

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

Published Aug 20, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s00037-026-00292-z

Related papers

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract

Shalev Ben-David, Eric Blais

We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions f and g such that R(f°g) ≪ R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of f). Second, we show that for all f and g, R(f°g) = Ω(noisyR(f) R(g)), where noisyR(f) is a measure describing the cost of computing f on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √n-gap majority function on n bits.

Annual Symposium on Foundations of Computer Science•Nov 1, 2020•9 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

Randomized query composition and sabotage complexity

Swagato Sanyal

Let \(\mathsf {R}_\epsilon\) denote the randomized query complexity for error probability ε, and \(\mathsf {R}:=\mathsf {R}_{1/3}\) . In this work, we investigate whether a perfect composition theorem \(\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {R}(g))\) holds for a relation \(f \subseteq \lbrace 0,1\rbrace ^n \times \mathcal {S}\) and a total inner function \(g:\lbrace 0,1\rbrace ^m \rightarrow \lbrace 0,1\rbrace\) . Ben-David and Kothari (ICALP 2016, TOC 2018) showed that \(\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {RS}(g))\) , where \(\mathsf {RS}\) is the sabotage complexity, a measure that they defined. Their result holds even when f is any relation and g is any partial function. Ben-David and Kothari asked in their article whether Sabotage complexity \(\mathsf {RS}\) is asymptotically equivalent to \(\mathsf {R}\) for total Boolean functions. In this article, we show that \(\mathsf {RS}\) is asymptotically at least the maximum distributional query complexity for any product distribution (i.e., probability distribution where the individual bits are independently distributed). In light of the minimax theorem, which states that \(\mathsf {R}\) is the maximum distributional query complexity for any distribution, our result makes progress toward answering the composition question. We prove our result by introducing a novel complexity measure called \(\mathsf {R}_{}^{\mathsf {prod}}\) , and proving it to be equivalent to \(\mathsf {RS}\) up to a logarithmic factor. How tight is our bound? We show that our bound is polynomially loose for the complete binary NAND tree function, for which \(\mathsf {RS}\) is polynomially larger than the distributional query complexity for any product distribution. Our result also confirms that \(\mathsf {RS}\) and \(\mathsf {R}\) are asymptotically equivalent for this function. We thus also show a polynomial separation between \(\mathsf {R}\) and the maximum distributional query complexity for any product distribution which, to our knowledge, was not known prior to our work.

ACM Transactions on Computation Theory•Jul 15, 2025•0 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•0 citations

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.

cs.CCCross-listedarXiv:2601.08073•Jan 14, 2026•0 citations

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions

Shalev Ben-David, Eric Blais

We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(f\circ g)\ll R(f) R(g)$. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$). Second, we show that for all $f$ and $g$, $R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))$, where $\mathop{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(\cdot)$ satisfying $R(f\circ g)=Ω(M(f)R(g))$ for all $f$ and $g$, it must hold that $\mathop{noisyR}(f)=Ω(M(f))$ for all $f$. We also give a clean characterization of the measure $\mathop{noisyR}(f)$: it satisfies $\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))$, where $n$ is the input size of $f$ and $gapmaj_n$ is the $\sqrt{n}$-gap majority function on $n$ bits.

arXiv:2002.10809•Feb 25, 2020•6 citations
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.
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions f and g such that R(f°g) ≪ R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of f). Second, we show that for all f and g, R(f°g) = Ω(noisyR(f) R(g)), where noisyR(f) is a measure describing the cost of computing f on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √n-gap majority function on n bits.
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.
Let Rϵ\mathsf {R}_\epsilonRϵ​ denote the randomized query complexity for error probability ε, and R:=R1/3\mathsf {R}:=\mathsf {R}_{1/3}R:=R1/3​ . In this work, we investigate whether a perfect composition theorem R(f∘gn)=Ω(R(f)⋅R(g))\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {R}(g))R(f∘gn)=Ω(R(f)⋅R(g)) holds for a relation f⊆{0,1}n×Sf \subseteq \lbrace 0,1\rbrace ^n \times \mathcal {S}f⊆{0,1}n×S and a total inner function g:{0,1}m→{0,1}g:\lbrace 0,1\rbrace ^m \rightarrow \lbrace 0,1\rbraceg:{0,1}m→{0,1} . Ben-David and Kothari (ICALP 2016, TOC 2018) showed that R(f∘gn)=Ω(R(f)⋅RS(g))\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {RS}(g))R(f∘gn)=Ω(R(f)⋅RS(g)) , where RS\mathsf {RS}RS is the sabotage complexity, a measure that they defined. Their result holds even when f is any relation and g is any partial function. Ben-David and Kothari asked in their article whether Sabotage complexity RS\mathsf {RS}RS is asymptotically equivalent to R\mathsf {R}R for total Boolean functions. In this article, we show that RS\mathsf {RS}RS is asymptotically at least the maximum distributional query complexity for any product distribution (i.e., probability distribution where the individual bits are independently distributed). In light of the minimax theorem, which states that R\mathsf {R}R is the maximum distributional query complexity for any distribution, our result makes progress toward answering the composition question. We prove our result by introducing a novel complexity measure called Rprod\mathsf {R}_{}^{\mathsf {prod}}Rprod​ , and proving it to be equivalent to RS\mathsf {RS}RS up to a logarithmic factor. How tight is our bound? We show that our bound is polynomially loose for the complete binary NAND tree function, for which RS\mathsf {RS}RS is polynomially larger than the distributional query complexity for any product distribution. Our result also confirms that RS\mathsf {RS}RS and R\mathsf {R}R are asymptotically equivalent for this function. We thus also show a polynomial separation between R\mathsf {R}R and the maximum distributional query complexity for any product distribution which, to our knowledge, was not known prior to our work.
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.
For a (possibly partial) Boolean function f ⁣:{0,1}n→{0,1}f\colon\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} as well as a query complexity measure MMM which maps Boolean functions to real numbers, define the composition limit of MMM on fff by M∗(f)=lim⁡k→∞M(fk)1/kM^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}M∗(f)=limk→∞​M(fk)1/k. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show R0∗(f)=max⁡{R∗(f),C∗(f)}R_0^*(f)=\max\{R^*(f),C^*(f)\}R0∗​(f)=max{R∗(f),C∗(f)}. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions fff and ggg such that R(f∘g)≪R(f)R(g)R(f\circ g)\ll R(f) R(g)R(f∘g)≪R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of fff). Second, we show that for all fff and ggg, R(f∘g)=Ω(noisyR(f)⋅R(g))R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))R(f∘g)=Ω(noisyR(f)⋅R(g)), where noisyR(f)\mathop{noisyR}(f)noisyR(f) is a measure describing the cost of computing fff on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(⋅)M(\cdot)M(⋅) satisfying R(f∘g)=Ω(M(f)R(g))R(f\circ g)=Ω(M(f)R(g))R(f∘g)=Ω(M(f)R(g)) for all fff and ggg, it must hold that noisyR(f)=Ω(M(f))\mathop{noisyR}(f)=Ω(M(f))noisyR(f)=Ω(M(f)) for all fff. We also give a clean characterization of the measure noisyR(f)\mathop{noisyR}(f)noisyR(f): it satisfies noisyR(f)=Θ(R(f∘gapmajn)/R(gapmajn))\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))noisyR(f)=Θ(R(f∘gapmajn​)/R(gapmajn​)), where nnn is the input size of fff and gapmajngapmaj_ngapmajn​ is the n\sqrt{n}n​-gap majority function on nnn bits.