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

ACM Transactions on Computation Theory

Randomized query composition and sabotage complexity

Swagato Sanyal

Published Jul 15, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1145/3747851

Related papers

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Miklós Sántha, Dmitry Gavinsky, Troy Lee +1 more

Let $R_\epsilon(\cdot)$ stand for the bounded-error randomized query complexity with error $\epsilon > 0$. For any relation $f \subseteq \{0,1\}^n \times S$ and partial Boolean function $g \subseteq \{0,1\}^m \times \{0,1\}$, we show that $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})$, where $f \circ g^n \subseteq (\{0,1\}^m)^n \times S$ is the composition of $f$ and $g$. We give an example of a relation $f$ and partial Boolean function $g$ for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity $\bar \chi(g)$ of a partial Boolean function $g$. We show $\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})$ for any (partial) function $g$ and $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))$; these two bounds imply our composition result. We further show that $\bar \chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.

•Jan 1, 2019•0 citations

No Perfect Randomized Composition

Alex Meiburg

Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions $f,g$ such that $R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)$ This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity $noisyR$, from standard randomized query complexity $R$. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage $RS$, max-conflict $\barχ$, and linearised query complexity $LR$. We show that AND-of-ORs separates conflict $χ$ from max-conflict $\barχ$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $Θ(\log R)$. The total--total composition separation is also formalized in Lean.

arXiv:2610.31638•Oct 22, 2026•0 citations

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Dmitry Gavinsky, Troy Lee, Miklós Sántha +1 more

For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.

arXiv:1811.10752•Leibniz international proceedings in informatics•Nov 27, 2018•4 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

Randomised Composition and Small-Bias Minimax

Shalev Ben-David, Eric Blais, Mika Göös +1 more

We prove1two results about randomised query complexity $\mathbf{R}(f)$. First, we introduce a linearised complexity measure LR and show that it satisfies an inner-optimal composition theorem: $\mathbf{R}(f^{\circ} g)\geq\Omega(\mathbf{R}(f)\mathbf{L R}(g))$ for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if $\epsilon$-error expected query complexity $\overline{\mathbf{R}}_{\epsilon}(f)$ admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case $\epsilon=1/2-o(1)$.1This is an extended abstract. For the full version of this article, please refer to [BDBGM22].

arXiv:2208.12896•Annual Symposium on Foundations of Computer Science•Oct 1, 2022•2 citations

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

cs.CCCross-listedarXiv:2609.15063•Sep 15, 2026•0 citations
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.
Let Rϵ(⋅)R_\epsilon(\cdot)Rϵ​(⋅) stand for the bounded-error randomized query complexity with error ϵ>0\epsilon > 0ϵ>0. For any relation f⊆{0,1}n×Sf \subseteq \{0,1\}^n \times Sf⊆{0,1}n×S and partial Boolean function g⊆{0,1}m×{0,1}g \subseteq \{0,1\}^m \times \{0,1\}g⊆{0,1}m×{0,1}, we show that R1/3(f∘gn)∈Ω(R4/9(f)⋅R1/3(g))R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})R1/3​(f∘gn)∈Ω(R4/9​(f)⋅R1/3​(g)​), where f∘gn⊆({0,1}m)n×Sf \circ g^n \subseteq (\{0,1\}^m)^n \times Sf∘gn⊆({0,1}m)n×S is the composition of fff and ggg. We give an example of a relation fff and partial Boolean function ggg for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity χˉ(g)\bar \chi(g)χˉ​(g) of a partial Boolean function ggg. We show χˉ(g)∈Ω(R1/3(g))\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})χˉ​(g)∈Ω(R1/3​(g)​) for any (partial) function ggg and R1/3(f∘gn)∈Ω(R4/9(f)⋅χˉ(g))R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))R1/3​(f∘gn)∈Ω(R4/9​(f)⋅χˉ​(g)); these two bounds imply our composition result. We further show that χˉ(g)\bar \chi(g)χˉ​(g) is always at least as large as the sabotage complexity of ggg, introduced by Ben-David and Kothari.
Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions f,gf,gf,g such that R(f∘g)=Θ ⁣(1log⁡R(g))R(f)R(g)R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)R(f∘g)=Θ(logR(g)1​)R(f)R(g) This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity noisyRnoisyRnoisyR, from standard randomized query complexity RRR. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage RSRSRS, max-conflict χˉ\barχχˉ​, and linearised query complexity LRLRLR. We show that AND-of-ORs separates conflict χχχ from max-conflict χˉ\barχχˉ​ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit R∗R^*R∗ by the maximal factor Θ(log⁡R)Θ(\log R)Θ(logR). The total--total composition separation is also formalized in Lean.
For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.
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.
We prove1two results about randomised query complexity R(f)\mathbf{R}(f)R(f). First, we introduce a linearised complexity measure LR and show that it satisfies an inner-optimal composition theorem: R(f∘g)≥Ω(R(f)LR(g))\mathbf{R}(f^{\circ} g)\geq\Omega(\mathbf{R}(f)\mathbf{L R}(g))R(f∘g)≥Ω(R(f)LR(g)) for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if ϵ\epsilonϵ-error expected query complexity R‾ϵ(f)\overline{\mathbf{R}}_{\epsilon}(f)Rϵ​(f) admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case ϵ=1/2−o(1)\epsilon=1/2-o(1)ϵ=1/2−o(1).1This is an extended abstract. For the full version of this article, please refer to [BDBGM22].