arXiv:1706.00335

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklós Sántha, Swagato Sanyal

Published Jun 1, 2017• 2 citations

arXiv HTML PDF

Abstract

Let the randomized query complexity of a relation for error probability $ε$ be denoted by $R_ε(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $R_{1/3}(f\circ g^n) = Ω(R_{4/9}(f)\cdot R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. We also show that $R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=Ω(\log n \cdot R_{4/9}(f) \cdot R_{1/3}(g))$, where $g^\oplus_{O(\log n)}$ is the function obtained by composing the xor function on $O(\log n)$ bits and $g^t$.

DOI: 10.48550/arxiv.1706.00335

Related papers

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5 more

Leibniz international proceedings in informaticsJan 1, 20182 citations

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

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

Jan 1, 20190 citations

Lifting randomized query complexity to randomized communication complexity

Anurag Anshu, Naresh Goud Boddu, Rahul Jain +2 more

We show that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ and a function $g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}$ (with $m= O(\log n)$), $$\mathrm{R}_{1/3}(f\circ g^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),$$ where $f\circ g^n$ represents the composition of $f$ and $g^n$, $M_g$ is the sign matrix for $g$, $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ($\mathrm{R}_{1/3}(f\circ g^n)$) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$) with worst case error $\frac{1}{3}$. In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$, $$\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot m\right),$$ where $\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}$ is the Inner Product (modulo $2$) function and $m= O(\log(n))$.

arXiv:1703.07521Electronic colloquium on computational complexityMar 22, 20172 citations

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

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

arXiv:1811.10752Leibniz international proceedings in informaticsNov 27, 20184 citations

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

cs.CCCross-listedarXiv:2601.08073Jan 14, 20260 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 TheoryJul 15, 20250 citations

arXiv:1706.00335

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklós Sántha, Swagato Sanyal

Published Jun 1, 2017• 2 citations

arXiv HTML PDF

Abstract

Let the randomized query complexity of a relation for error probability

ε

be denoted by

R_ε(\cdot)

. We prove that for any relation

f \subseteq \{0,1\}^n \times \mathcal{R}

and Boolean function

g:\{0,1\}^m \rightarrow \{0,1\}

R_{1/3}(f\circ g^n) = Ω(R_{4/9}(f)\cdot R_{1/2-1/n^4}(g))

, where

f \circ g^n

is the relation obtained by composing

f

and

g

. We also show that

R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=Ω(\log n \cdot R_{4/9}(f) \cdot R_{1/3}(g))

, where

g^\oplus_{O(\log n)}

is the function obtained by composing the xor function on

O(\log n)

bits and

g^t

DOI: 10.48550/arxiv.1706.00335

Related papers

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5 more

Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.

Leibniz international proceedings in informaticsJan 1, 20182 citations

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.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, 20190 citations

Lifting randomized query complexity to randomized communication complexity

Anurag Anshu, Naresh Goud Boddu, Rahul Jain +2 more

We show that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ and a function $g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}$ (with $m= O(\log n)$ ), $\mathrm{R}_{1/3}(f\circ g^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),$ where $f\circ g^n$ represents the composition of $f$ and $g^n$ , $M_g$ is the sign matrix for $g$ , $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ( $\mathrm{R}_{1/3}(f\circ g^n)$ ) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$ ) with worst case error $\frac{1}{3}$ . In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ , $\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot m\right),$ where $\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}$ is the Inner Product (modulo $2$ ) function and $m= O(\log(n))$ .We show that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ and a function $g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}$ (with $m= O(\log n)$), $$\mathrm{R}_{1/3}(f\circ g^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),$$ where $f\circ g^n$ represents the composition of $f$ and $g^n$, $M_g$ is the sign matrix for $g$, $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ($\mathrm{R}_{1/3}(f\circ g^n)$) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$) with worst case error $\frac{1}{3}$. In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$, $$\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot m\right),$$ where $\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}$ is the Inner Product (modulo $2$) function and $m= O(\log(n))$.

arXiv:1703.07521Electronic colloquium on computational complexityMar 22, 20172 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.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.10752Leibniz international proceedings in informaticsNov 27, 20184 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.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.08073Jan 14, 20260 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.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 TheoryJul 15, 20250 citations

Let the randomized query complexity of a relation for error probability

ε

be denoted by

R_ε(\cdot)

. We prove that for any relation

f \subseteq \{0,1\}^n \times \mathcal{R}

and Boolean function

g:\{0,1\}^m \rightarrow \{0,1\}

R_{1/3}(f\circ g^n) = Ω(R_{4/9}(f)\cdot R_{1/2-1/n^4}(g))

, where

f \circ g^n

is the relation obtained by composing

f

and

g

. We also show that

R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=Ω(\log n \cdot R_{4/9}(f) \cdot R_{1/3}(g))

, where

g^\oplus_{O(\log n)}

is the function obtained by composing the xor function on

O(\log n)

bits and

g^t

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.

We show that for a relation

f\subseteq \{0,1\}^n\times \mathcal{O}

and a function

g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}

(with

m= O(\log n)

\mathrm{R}_{1/3}(f\circ g^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),

where

f\circ g^n

represents the composition of

f

and

g^n

M_g

is the sign matrix for

g

\mathrm{disc}(M_g)

is the discrepancy of

M_g

under the uniform distribution and

\mathrm{R}_{1/3}(f)

(

\mathrm{R}_{1/3}(f\circ g^n)

) denotes the randomized query complexity of

f

(randomized communication complexity of

f\circ g^n

) with worst case error

\frac{1}{3}

. In particular, this implies that for a relation

f\subseteq \{0,1\}^n\times \mathcal{O}

\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = Ω\left(\mathrm{R}_{1/3}(f) \cdot m\right),

where

\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}

is the Inner Product (modulo

2

) function and

m= O(\log(n))

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

f

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.

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.