13
$\begingroup$

Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main challenges? Which techniques may be amenable to make any progress? Any observation (irrespective of whether it is insightful or not; trivial or not) is also welcome.

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.

We define the zero error or 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 bounded error or 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 $\geq$ $1 - \delta$ ($2/3$, say).


Work on Recursive Boolean Functions:

There has been a line of work on the decision tree complexity of recursive boolean functions as mentioned below. The techniques focus on applying Yao's Lemma and using the distributional perspective guaranteed by it. This means we define a probability distribution on the inputs and the cost incurred by the best algorithm for this distribution gives a lower bound on the randomized decision tree complexity of the function. The worst possible distribution will give the actual randomized decision tree complexity.

The techniques in these works focus on giving a lower bound on the cost incurred by reading the "minority" bits (or vertices in the function tree) of the input via some form of induction. Another direction of attack could be to find the most "hard" distribution.


Some Notions

We define: The distribution $D^*$ on an input set $I$ is hard for a given function $f$, if $\forall D$ on $I$, $C(A,D) \leq C(A^*, D^*) $, where $C(A,D)$ is the expected cost (i.e. number of input bits read on expectation) incurred by the deterministic decision tree $A$ when the input follows the probability distribution is $D$. where $A^* = \operatorname{argmin}_A C(A, D^*), A = \operatorname{argmin}_A C(A, D)$

A distribution $D_1 < D_2$, if $C_m(D_1) < C_m(D_2)$, where $C_m(D_i) = C(A_i, D_i)$, and $A_i = \operatorname{argmin}_A C(A, D_i)$ . In other words $D_2$ is harder than $D_1$ means the best possible algorithm for $D_2$ does worse than the best possible algorithm for $D_1$. Note: The algorithm must be correct in the whole domain, and not just in the support of the distributions. For the base case of a recursive boolean function like say 2 bits or 4 bits, it is often easy to show a certain distribution to be hard. Often it is an easy observation or an obvious fact. In many cases, it may seem natural that the "hard" distribution is the recursive extension of the hard distribution. However, this may not be true in general, especially if the function is not symmetric over the input bits and rather skewed i.e. not all input bits are equally important to infer the value of the function on certain inputs (or a subset thereof).

Question:

Is there any work on how to approach the problem of finding the "hard" distribution of the recursive function, from that of the base case function?

Is there any interesting connection of this problem with any other problems? Any comments are welcome.

References:

[1] M. Saks, A. Wigderson Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees Proceedings of the 27th Foundations of Computer Science, pp. 29-38, October 1986.

[2] M. Santha. On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures and Algorithms, 6(1):75{87, 1995.

[3] Frédéric Magniez, Ashwin Nayak, Miklos Santha, and David Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. In Luca Aceto, Monika Henzinger, and Jiri Sgall, editors, ICALP (1), volume 6755 of Lecture Notes in Computer Science, pages 317–329. Springer, 2011.

[3a]Frederic Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gabor Tardos, David Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. http://arxiv.org/abs/1309.7565 (Submitted on 29 Sep 2013)

[4] Nikos Leonardos. An improved lower bound for the randomized decision tree complexity of recursive majority. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Proceedings of 40th International Colloquium on Automata, Languages and Programming, volume 7965 of Lecture Notes in Computer Science, pages 696{708. Springer, 2013.

$\endgroup$
  • $\begingroup$ you mean "hard" wrt decision tree complexity right? $\endgroup$ – vzn Jul 22 '14 at 15:12
  • 1
    $\begingroup$ As far as I know, this isn't even known for the recursive majority of 3 function studied by refs [3] and [4] in your question, right? For that function, the conjectured hard distribution seems like it must be the hard distribution, but we still don't know how to prove that. $\endgroup$ – Robin Kothari Jul 28 '14 at 14:25
  • 1
    $\begingroup$ @Jardine: I don't know if there's been much work on this other than the papers you cited. The only somewhat relevant work I know is due to Kazuyuki Amano, "Bounding the Rondomized Decision Tree Complexity of Read-Once Boolean Functions" (SODA 2011). Other than this, all I can say is that I'm pretty sure the obvious hard distribution has not been proven to be the hard distribution for recursive 3-MAJ. $\endgroup$ – Robin Kothari Jul 29 '14 at 18:21
  • 1
    $\begingroup$ @Jardine: I haven't studied the problem in detail, so I can't say much. 3-MAJ seems like the first function to attack to try to understand this general question, especially since the function has been studied in several papers. Maybe someone who has studied the problem can give you a better answer. $\endgroup$ – Robin Kothari Jul 31 '14 at 23:39
  • 1
    $\begingroup$ I really don't understand your question - finding the hard distribution would be almost equivalent (supposing we can solve the deterministic problem) to calculating the randomized complexity. Also, your citations are outdated, see arxiv.org/abs/1309.7565. $\endgroup$ – domotorp Aug 21 '14 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.