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

Optimal Separation and Strong Direct Sum for Randomized Query Complexity

Eric Blais, Joshua Brody

Published Jan 1, 2019• 8 citations
arXivHTMLPDF

Abstract

We establish two results regarding the query complexity of bounded-error randomized algorithms. Bounded-error separation theorem. There exists a total function f : {0,1}^n -> {0,1} whose epsilon-error randomized query complexity satisfies overline{R}_epsilon(f) = Omega(R(f) * log 1/epsilon). Strong direct sum theorem. For every function f and every k >= 2, the randomized query complexity of computing k instances of f simultaneously satisfies overline{R}_epsilon(f^k) = Theta(k * overline{R}_{epsilon/k}(f)). As a consequence of our two main results, we obtain an optimal superlinear direct-sum-type theorem for randomized query complexity: there exists a function f for which R(f^k) = Theta(k log k * R(f)). This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of Göös, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies R^{cc}(f^k) = Theta(k log k * R^{cc}(f)), answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).

DOI
10.4230/lipics.ccc.2019.29

Related papers

Direct sum theorems beyond query complexity

Daiki Suruga

A fundamental question in computer science is: Is it harder to solve $n$ instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function $f: \{0, 1\}^k \to \{0, 1\}$ and small error $\varepsilon > 0$ such that solving $n$ instances simultaneously requires the query complexity $\tilde{O}(n\sqrt{k})$ but solving one instance with the same error has the complexity $\tildeΩ(k)$. In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.

arXiv:2408.15570•Aug 28, 2024•0 citations

A Strong XOR Lemma for Randomized Query Complexity

Brody, Joshua, Jae Tak Kim, Peem Lerdputtipongporn +1 more

We give a strong direct sum theorem for computing $xor \circ g$. Specifically, we show that for every function g and every $k\geq 2$, the randomized query complexity of computing the xor of k instances of g satisfies $\overline{R}_\eps(xor\circ g) = Θ(k \overline{R}_{\eps/k}(g))$. This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC19). As a consequence of our strong direct sum theorem, we give a total function g for which $R(xor \circ g) = Θ(k \log(k)\cdot R(g))$, answering an open question from Ben-David et al.(arxiv:2006.10957v1).

arXiv:2007.05580•Jul 10, 2020•4 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

Separations in Query Complexity Based on Pointer Functions

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3 more

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

arXiv:1506.04719•Journal of the ACM•Sep 4, 2017•28 citations

Zero-error expectation equals amortized query complexity

Daiki Suruga

This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation $f$ and any error tolerance $\varepsilon \in [0,1]$, we prove \[ \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). \] Thus the amortization converts bounded-error into zero error with the exact multiplicative factor $1-\varepsilon$. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function $\operatorname{OR}_n \circ f$, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.

arXiv:2608.04152•Aug 4, 2026•0 citations

Direct Product Theorems for Randomized Query Complexity

Shalev Ben-David, Blais, Eric

We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing $n$ copies of a function $f$, even with a small success probability of $γ^n$, requires $Θ(n)$ times the "maximum distributional" query complexity of $f$ with success parameter $γ$. This result holds for all success parameters $γ$, even when $γ$ is very close to $1/2$ or to $1$. As a result, it unifies and generalizes Drucker's direct product theorem (2012) for $γ$ bounded away from $\frac12$ and $1$ as well as the strong direct sum theorem of Blais and Brody (2019) for $γ\approx 1-1/n$. The second establishes a general "list decoding" direct product theorem that captures many different variants of partial computation tasks related to the function $f^n$ consisting of $n$ copies of $f$. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call "discounted score". We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.

arXiv:2512.08268•Dec 9, 2025•0 citations
We establish two results regarding the query complexity of bounded-error randomized algorithms. Bounded-error separation theorem. There exists a total function f : {0,1}^n -> {0,1} whose epsilon-error randomized query complexity satisfies overline{R}_epsilon(f) = Omega(R(f) * log 1/epsilon). Strong direct sum theorem. For every function f and every k >= 2, the randomized query complexity of computing k instances of f simultaneously satisfies overline{R}epsilon(f^k) = Theta(k * overline{R}{epsilon/k}(f)). As a consequence of our two main results, we obtain an optimal superlinear direct-sum-type theorem for randomized query complexity: there exists a function f for which R(f^k) = Theta(k log k * R(f)). This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of Göös, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies R^{cc}(f^k) = Theta(k log k * R^{cc}(f)), answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).
A fundamental question in computer science is: Is it harder to solve nnn instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function f:{0,1}k→{0,1}f: \{0, 1\}^k \to \{0, 1\}f:{0,1}k→{0,1} and small error ε>0\varepsilon > 0ε>0 such that solving nnn instances simultaneously requires the query complexity O~(nk)\tilde{O}(n\sqrt{k})O~(nk​) but solving one instance with the same error has the complexity Ω~(k)\tildeΩ(k)Ω~(k). In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.
We give a strong direct sum theorem for computing xor∘gxor \circ gxor∘g. Specifically, we show that for every function g and every k≥2k\geq 2k≥2, the randomized query complexity of computing the xor of k instances of g satisfies $\overline{R}_\eps(xor\circ g) = Θ(k \overline{R}_{\eps/k}(g))$. This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC19). As a consequence of our strong direct sum theorem, we give a total function g for which R(xor∘g)=Θ(klog⁡(k)⋅R(g))R(xor \circ g) = Θ(k \log(k)\cdot R(g))R(xor∘g)=Θ(klog(k)⋅R(g)), answering an open question from Ben-David et al.(arxiv:2006.10957v1).
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation fff and any error tolerance ε∈[0,1]\varepsilon \in [0,1]ε∈[0,1], we prove lim⁡n→∞R‾ε(fn)n=(1−ε)R‾0(f). \lim_{n \to \infty} \frac{\overline{R}_\varepsilon(f^n)}{n} = (1 - \varepsilon) \overline{R}_0(f). limn→∞​nRε​(fn)​=(1−ε)R0​(f). Thus the amortization converts bounded-error into zero error with the exact multiplicative factor 1−ε1-\varepsilon1−ε. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function OR⁡n∘f\operatorname{OR}_n \circ fORn​∘f, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.
We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing nnn copies of a function fff, even with a small success probability of γnγ^nγn, requires Θ(n)Θ(n)Θ(n) times the "maximum distributional" query complexity of fff with success parameter γγγ. This result holds for all success parameters γγγ, even when γγγ is very close to 1/21/21/2 or to 111. As a result, it unifies and generalizes Drucker's direct product theorem (2012) for γγγ bounded away from 12\frac1221​ and 111 as well as the strong direct sum theorem of Blais and Brody (2019) for γ≈1−1/nγ\approx 1-1/nγ≈1−1/n. The second establishes a general "list decoding" direct product theorem that captures many different variants of partial computation tasks related to the function fnf^nfn consisting of nnn copies of fff. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call "discounted score". We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.