<p>As far as I know, this is still open. A very recent paper that mentions these quantities and some bounds is Aaronson et al: Weak parity (see <a href="http://arxiv.org/abs/1312.0036">http://arxiv.org/abs/1312.0036</a>). You can also see chapter 14 of Jukna: Boolean funcions and the 1999 (still beats 1998!) survey by Buhrman and de Wolf. Another very recent paper about randomized decision tree complexity is Magniez et al: <a href="http://arxiv.org/abs/1309.7565">http://arxiv.org/abs/1309.7565</a></p>

<p>Finally, a short summary I made for myself last month (without defs):</p>

<p>R2&lt;=R0&lt;=D&lt;=n</p>

<p>D&lt;=N0*N1&lt;=C^2&lt;=R0^2</p>

<p>s&lt;=bs&lt;=C&lt;=s*bs&lt;=bs^2 (new: [Gilmer-Saks-Srinivasan]: there is f s.t. bs^2(f)=O(C(f)))</p>

<p>D&lt;=N1*bs&lt;=bs^3&lt;=(3R2)^3</p>

<p>deg&lt;=D&lt;=bs*deg&lt;=deg^3 (new: [Tal]: bs&lt;=deg^2)</p>

<p>D&lt;=N1*deg</p>

<p>C&lt;=bs*deg^2&lt;=deg^4</p>

<p>Sensitivity conjecture is that s is also polynomially related to other parameters.</p>

CC BY-SA 3.0
2014-05-25T20:32:45.033Z
Could you point out specifically where these papers reference the question of Las Vegas vs Monte Carlo algorithms? I tried to look for it in these papers but couldn't find it.
Robin Kothari
CC BY-SA 3.0
2014-05-25T21:19:54.297Z
I am sorry if I was ambiguous, these papers do not explicitly mention the question, only different inequalities for the different parameters. My only evidence for the openness of the question is that if it were not, it would be mentioned.
domotorp
CC BY-SA 3.0
2014-05-25T22:28:41.267Z
Oh, I understand what you mean. I have read these papers. I wonder if this problem has been studied specifically more recently though. And I'm also curious to know if there's a function that is conjectured to separate these two complexities. (Or if people believe they are the same.)
Robin Kothari
CC BY-SA 3.0
2014-05-26T08:10:31.130Z
I know that it is conjectured that the biggest separation from D is the NAND-tree for both R0 and R2.
domotorp
CC BY-SA 3.0
2014-05-25T19:22:28.477Z
2014-05-25T21:23:35.673Z
2014-05-25T21:23:35.673Z
domotorp
<p>This question has been resolved! </p>

<p>A few days ago <a href="http://arxiv.org/abs/1506.04719" rel="nofollow">Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs</a> uploaded a preprint showing the existence of a total function $f$ which satisfies</p>

<blockquote>
  <p>$R_0(f) = \tilde{\Omega}(R_2(f)^{2})$</p>
</blockquote>

<p>and even </p>

<blockquote>
  <p>$R_0(f) = \tilde{\Omega}(R_1(f)^{2})$,</p>
</blockquote>

<p>where $R_1(f)$ denotes 1-sided bounded-error randomized query complexity.</p>

<p>Both separations are optimal up to log factors!</p>

CC BY-SA 3.0
2015-09-01T05:05:46.343Z
In the new version of their paper, this has been improved to a nearly-quadratic gap, which is tight up to log factors.
Shalev
CC BY-SA 3.0
2015-06-21T20:02:03.663Z
2015-09-01T14:12:09.977Z
2015-09-01T14:12:09.977Z
Robin Kothari
<h2>Background:</h2>

<p><a href="https://en.wikipedia.org/wiki/Query_complexity" rel="nofollow">Decision tree complexity</a> or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of $f$, denoted $D(f)$, is the minimum number of bits of the input $x\in\{0,1\}^n$ that need to be read (in the worse case) by a deterministic algorithm that computes $f(x)$. Note that the measure of complexity is the number of bits of the input that are read; all other computation is free.</p>

<p>Similarly, we define the Las Vegas randomized query complexity of $f$, denoted $R_0(f)$, as the minimum number of input bits that need to be read in expectation by a zero-error randomized algorithm that computes $f(x)$. A zero-error algorithm always outputs the correct answer, but the number of input bits read by it depends on the internal randomness of the algorithm. (This is why we measure the expected number of input bits read.)</p>

<p>We define the Monte Carlo randomized query complexity of $f$, denoted $R_2(f)$, to be the minimum number of input bits that need to be read by a bounded-error randomized algorithm that computes $f(x)$. A bounded-error algorithm always outputs an answer at the end, but it only needs to be correct with probability greater than $2/3$ (say).</p>

<hr>

<h2>Question</h2>

<p>What is known about the question of whether </p>

<blockquote>
  <p>$R_0(f) = \Theta(R_2(f))$?</p>
</blockquote>

<p>It is known that  </p>

<blockquote>
  <p>$R_0(f) = \Omega(R_2(f))$</p>
</blockquote>

<p>because Monte Carlo algorithms are at least as powerful as Las Vegas algorithms. </p>

<p>I recently learned that there is no known separation between the two complexities. The latest reference I can find for this claim is from 1998 [1]:</p>

<p>[1] Nikolai K. Vereshchagin, Randomized Boolean decision trees: Several remarks, Theoretical Computer Science, Volume 207, Issue 2, 6 November 1998, Pages 329-342, ISSN 0304-3975, <a href="http://dx.doi.org/10.1016/S0304-3975(98)00071-1" rel="nofollow">http://dx.doi.org/10.1016/S0304-3975(98)00071-1</a>.</p>

<p>The best known upper bound of one in terms of the other is</p>

<blockquote>
  <p>$R_0(f) = O(R_2(f)^2 \log{R_2(f)})$</p>
</blockquote>

<p>due to [2]:</p>

<p>[2] Kulkarni, R., &amp; Tal, A. (2013, November). On Fractional Block Sensitivity. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, p. 168).</p>

<p>I have two specific questions.</p>

<ol>
<li>[Reference request]: Is there a more recent paper (after 1998) that discusses this problem?</li>
<li><strong>More importantly</strong>, is there a candidate function that is conjectured to separate these two complexities?</li>
</ol>

<p><strong>Added in v2:</strong> Added ref [2], emphasized second question about existence of candidate function.</p>

<cc.complexity-theory><reference-request><query-complexity><decision-trees>
Las Vegas vs Monte Carlo randomized decision tree complexity
Robin Kothari
# Las Vegas vs Monte Carlo randomized decision tree complexity

(Asked by: username_0 on 2014-05-25)

## Background:

[Decision tree complexity](https://en.wikipedia.org/wiki/Query_complexity) or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of $f$, denoted $D(f)$, is the minimum number of bits of the input $x\in\{0,1\}^n$ that need to be read (in the worse case) by a deterministic algorithm that computes $f(x)$. Note that the measure of complexity is the number of bits of the input that are read; all other computation is free.

Similarly, we define the Las Vegas randomized query complexity of $f$, denoted $R\_0(f)$, as the minimum number of input bits that need to be read in expectation by a zero-error randomized algorithm that computes $f(x)$. A zero-error algorithm always outputs the correct answer, but the number of input bits read by it depends on the internal randomness of the algorithm. (This is why we measure the expected number of input bits read.)

We define the Monte Carlo randomized query complexity of $f$, denoted $R\_2(f)$, to be the minimum number of input bits that need to be read by a bounded-error randomized algorithm that computes $f(x)$. A bounded-error algorithm always outputs an answer at the end, but it only needs to be correct with probability greater than $2/3$ (say).

---

## Question

What is known about the question of whether

> $R\_0(f) = \Theta(R\_2(f))$?

It is known that

> $R\_0(f) = \Omega(R\_2(f))$

because Monte Carlo algorithms are at least as powerful as Las Vegas algorithms.

I recently learned that there is no known separation between the two complexities. The latest reference I can find for this claim is from 1998 [1]:

[1] Nikolai K. Vereshchagin, Randomized Boolean decision trees: Several remarks, Theoretical Computer Science, Volume 207, Issue 2, 6 November 1998, Pages 329-342, ISSN 0304-3975, <http://dx.doi.org/10.1016/S0304-3975(98)00071-1>.

The best known upper bound of one in terms of the other is

> $R\_0(f) = O(R\_2(f)^2 \log{R\_2(f)})$

due to [2]:

[2] Kulkarni, R., & Tal, A. (2013, November). On Fractional Block Sensitivity. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, p. 168).

I have two specific questions.

1. [Reference request]: Is there a more recent paper (after 1998) that discusses this problem?
2. **More importantly**, is there a candidate function that is conjectured to separate these two complexities?

**Added in v2:** Added ref [2], emphasized second question about existence of candidate function.

**Tags:** cc.complexity-theory, reference-request, query-complexity, decision-trees

---

## 2 answers

### Answer by username_0 on 2015-06-21. Score: 7 | Accepted answer

This question has been resolved!

A few days ago [Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs](http://arxiv.org/abs/1506.04719) uploaded a preprint showing the existence of a total function $f$ which satisfies

> $R\_0(f) = \tilde{\Omega}(R\_2(f)^{2})$

and even

> $R\_0(f) = \tilde{\Omega}(R\_1(f)^{2})$,

where $R\_1(f)$ denotes 1-sided bounded-error randomized query complexity.

Both separations are optimal up to log factors!

> **Comments:**
> **username_2**: In the new version of their paper, this has been improved to a nearly-quadratic gap, which is tight up to log factors.  

---

### Answer by username_1 on 2014-05-25. Score: 7

As far as I know, this is still open. A very recent paper that mentions these quantities and some bounds is Aaronson et al: Weak parity (see <http://arxiv.org/abs/1312.0036>). You can also see chapter 14 of Jukna: Boolean funcions and the 1999 (still beats 1998!) survey by Buhrman and de Wolf. Another very recent paper about randomized decision tree complexity is Magniez et al: <http://arxiv.org/abs/1309.7565>

Finally, a short summary I made for myself last month (without defs):

R2<=R0<=D<=n

D<=N0\*N1<=C^2<=R0^2

s<=bs<=C<=s\*bs<=bs^2 (new: [Gilmer-Saks-Srinivasan]: there is f s.t. bs^2(f)=O(C(f)))

D<=N1\*bs<=bs^3<=(3R2)^3

deg<=D<=bs\*deg<=deg^3 (new: [Tal]: bs<=deg^2)

D<=N1\*deg

C<=bs\*deg^2<=deg^4

Sensitivity conjecture is that s is also polynomially related to other parameters.

> **Comments:**
> **username_0**: Could you point out specifically where these papers reference the question of Las Vegas vs Monte Carlo algorithms? I tried to look for it in these papers but couldn't find it.  
> **username_1**: I am sorry if I was ambiguous, these papers do not explicitly mention the question, only different inequalities for the different parameters. My only evidence for the openness of the question is that if it were not, it would be mentioned.  
> **username_0**: Oh, I understand what you mean. I have read these papers. I wonder if this problem has been studied specifically more recently though. And I'm also curious to know if there's a function that is conjectured to separate these two complexities. (Or if people believe they are the same.)  
> **username_1**: I know that it is conjectured that the biggest separation from D is the NAND-tree for both R0 and R2.  

---

