Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.


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


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.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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



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


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



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

share|improve this answer
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 May 25 '14 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. –  domotorp May 25 '14 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.) –  Robin Kothari May 25 '14 at 22:28
I know that it is conjectured that the biggest separation from D is the NAND-tree for both R0 and R2. –  domotorp May 26 '14 at 8:10
I'm going to accept this for now, unless someone answers my second question. –  Robin Kothari Mar 12 at 11:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.