# Las Vegas vs Monte Carlo randomized decision tree complexity

## 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?

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.

• 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. May 25, 2014 at 20:32
• 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. May 25, 2014 at 21:19
• 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.) May 25, 2014 at 22:28
• I know that it is conjectured that the biggest separation from D is the NAND-tree for both R0 and R2. May 26, 2014 at 8:10

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!

• In the new version of their paper, this has been improved to a nearly-quadratic gap, which is tight up to log factors. Sep 1, 2015 at 5:05