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:2006.10957 · Leibniz international proceedings in informatics

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Shalev Ben-David, Mika Göös, Robin Kothari, Thomas W. Watson

Published Jan 1, 2020• 7 citations
arXivHTMLPDF

Abstract

Suppose we have randomized decision trees for an outer function $f$ and an inner function $g$. The natural approach for obtaining a randomized decision tree for the composed function $(f\circ g^n)(x^1,\ldots,x^n)=f(g(x^1),\ldots,g(x^n))$ involves amplifying the success probability of the decision tree for $g$, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.

DOI
10.4230/lipics.approx/random.2020.28

Related papers

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n³) and randomized parity decision tree complexity Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif [Chattopadhyay et al., 2020] both qualitatively (in terms of designing a large number of examples) and quantitatively (shrinking the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).

Leibniz international proceedings in informatics•Jan 1, 2021•5 citations

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Θ(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).

arXiv:2009.02717•Sep 6, 2020•1 citation

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture.

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).

Electronic colloquium on computational complexity•Jan 1, 2020•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

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

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
Suppose we have randomized decision trees for an outer function fff and an inner function ggg. The natural approach for obtaining a randomized decision tree for the composed function (f∘gn)(x1,…,xn)=f(g(x1),…,g(xn))(f\circ g^n)(x^1,\ldots,x^n)=f(g(x^1),\ldots,g(x^n))(f∘gn)(x1,…,xn)=f(g(x1),…,g(xn)) involves amplifying the success probability of the decision tree for ggg, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n³) and randomized parity decision tree complexity Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif [Chattopadhyay et al., 2020] both qualitatively (in terms of designing a large number of examples) and quantitatively (shrinking the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on nnn input bits, each of which has approximate Fourier sparsity at most O(n3)O(n^3)O(n3) and randomized parity decision tree complexity Θ(n)Θ(n)Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on nnn input bits, each of which has approximate Fourier sparsity at most O(n3)O(n^3)O(n3) and randomized parity decision tree complexity Θ(n)\Theta(n)Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
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.
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 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.