arXiv:1703.07521 · Electronic colloquium on computational complexity

Lifting randomized query complexity to randomized communication complexity

Anurag Anshu, Naresh Goud Boddu, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

Published Mar 22, 2017• 2 citations

Abstract

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))$.

DOI: 10.48550/arxiv.1703.07521

Related papers

A Composition Theorem for Randomized Query Complexity

Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5 more

arXiv:1706.00335Jun 1, 20172 citations

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

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

Separation Between Deterministic and Randomized Query Complexity

Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal

SIAM Journal on ComputingJan 1, 20183 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

arXiv:1703.07521 · Electronic colloquium on computational complexity

Lifting randomized query complexity to randomized communication complexity

Anurag Anshu, Naresh Goud Boddu, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

Published Mar 22, 2017• 2 citations

arXiv HTML PDF

Abstract

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))

DOI: 10.48550/arxiv.1703.07521

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 $ε$ 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 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$.

arXiv:1706.00335Jun 1, 20172 citations

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

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

Separation Between Deterministic and Randomized Query Complexity

Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal

Saks and Wigderson [in Proceedings of the $27$ th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that $R_0(f) = \Omega(D(f)^{0.753\ldots})$ for all Boolean functions $f$ , where $R_0$ denotes the randomized zero-error query complexity and $D$ denotes the deterministic query complexity. We show that for the pointer function $\mathsf{GPW}^{r \times s}$ defined by Göös, Pitassi, and Watson [in Proceedings of the $56$ th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) $R_1(\mathsf{GPW}^{r \times s}) = \widetilde{\Theta}({r+s})$ and (b) $R_1(\overline{\mathsf{GPW}^{r \times s}}) = \widetilde{\Theta}(r+\sqrt{r}s)$ , where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(\mathsf{GPW}^{s^2 \times s}) = O(D(\mathsf{GPW}^{s^2 \times s})^{2/3})$ , thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(\mathsf{GPW}^{s \times s})=\widetilde{O}(R_0(\mathsf{GPW}^{s \times s})^{2/3})$ , thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.Saks and Wigderson [in Proceedings of the $27$th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that $R_0(f) = \Omega(D(f)^{0.753\ldots})$ for all Boolean functions $f$, where $R_0$ denotes the randomized zero-error query complexity and $D$ denotes the deterministic query complexity. We show that for the pointer function $\mathsf{GPW}^{r \times s}$ defined by Göös, Pitassi, and Watson [in Proceedings of the $56$th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) $R_1(\mathsf{GPW}^{r \times s}) = \widetilde{\Theta}({r+s})$ and (b) $R_1(\overline{\mathsf{GPW}^{r \times s}}) = \widetilde{\Theta}(r+\sqrt{r}s)$, where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(\mathsf{GPW}^{s^2 \times s}) = O(D(\mathsf{GPW}^{s^2 \times s})^{2/3})$, thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(\mathsf{GPW}^{s \times s})=\widetilde{O}(R_0(\mathsf{GPW}^{s \times s})^{2/3})$, thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.

SIAM Journal on ComputingJan 1, 20183 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

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))

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.

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.

Saks and Wigderson [in Proceedings of the

27

th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that

R_0(f) = \Omega(D(f)^{0.753\ldots})

for all Boolean functions

f

, where

R_0

denotes the randomized zero-error query complexity and

D

denotes the deterministic query complexity. We show that for the pointer function

\mathsf{GPW}^{r \times s}

defined by Göös, Pitassi, and Watson [in Proceedings of the

56

th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a)

R_1(\mathsf{GPW}^{r \times s}) = \widetilde{\Theta}({r+s})

and (b)

R_1(\overline{\mathsf{GPW}^{r \times s}}) = \widetilde{\Theta}(r+\sqrt{r}s)

, where

R_1

denotes the randomized one-sided error query complexity. These results imply that (i)

R_0(\mathsf{GPW}^{s^2 \times s}) = O(D(\mathsf{GPW}^{s^2 \times s})^{2/3})

, thereby refuting the conjecture of Saks and Wigderson, and (ii)

R_1(\mathsf{GPW}^{s \times s})=\widetilde{O}(R_0(\mathsf{GPW}^{s \times s})^{2/3})

, thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.