Las Vegas vs Monte Carlo randomized decision tree complexity

Question

Background:

Decision tree 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.

Answer 1

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.

Answer 2

This question has been resolved!

A few days ago Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs 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!