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:1605.09071 · Electronic colloquium on computational complexity

Randomized query complexity of sabotaged and composed functions

Shalev Ben-David, Robin Kothari

Published May 29, 2016• 11 citations
arXivHTMLPDF

Abstract

We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f o h o g) = Omega(R(f) R(h) R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f o g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f o g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem for zero-error randomized protocols implies a general lifting theorem for bounded-error protocols.

DOI
10.48550/arxiv.1605.09071

Related papers

Randomized Query Complexity of Sabotaged and Composed Functions

Shalev Ben-David, Robin Kothari

We study the composition question for bounded-error randomized query complexity: Is R(f circ g) = Omega(R(f)R(g))? We show that inserting a simple function h, whose query complexity is onlyTheta(log R(g)), in between f and g allows us to prove R(f circ h circ g) = Omega(R(f)R(h)R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f circ g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f circ g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem from zero-error randomized query to communication complexity implies a similar result for bounded-error algorithms for all total functions.

Leibniz international proceedings in informatics•Jan 1, 2016•9 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

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

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

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•23 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
We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f o h o g) = Omega(R(f) R(h) R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f o g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f o g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem for zero-error randomized protocols implies a general lifting theorem for bounded-error protocols.
We study the composition question for bounded-error randomized query complexity: Is R(f circ g) = Omega(R(f)R(g))? We show that inserting a simple function h, whose query complexity is onlyTheta(log R(g)), in between f and g allows us to prove R(f circ h circ g) = Omega(R(f)R(h)R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f circ g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f circ g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem from zero-error randomized query to communication complexity implies a similar result for bounded-error algorithms for all total functions.
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.
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.
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.
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.