# Provable gaps between decision tree complexity and “true” complexity

The title is a little misleading: but hopefully the question isn't:

Grønlund and Pettie's new result showing that 3SUM has only $O(n^{3/2})$ decision tree complexity got me wondering:

Is there a simple example of a problem with a decision tree complexity of $O(f)$ but that admits a lower bound (in a more detailed model) of $\omega(f)$ ?

In other words, how should the result on 3SUM change our view of the possibility of getting a significantly lower than $n^2$ upper bound on the complexity of the problem ?

-
Element distinctness can be solved with a constant-depth binary decision tree. ("Are all the elements distinct?") But we need $\Omega(n\log n)$ depth to solve the problem using using linear decision trees. –  JɛﬀE Apr 12 '14 at 1:31
The decision tree model is an information theoretic model: Once you have learned enough information about your input that the answer is uniquely determined from this information, you are done. It doesn't matter if determining the answer from this information is undecidable. So for example if the input is an n-bit binary string encoding a Turing machine, and the question is whether this TM halts, a decision tree of depth n can trivially solve this problem since it knows all n bits, but no algorithm can solve this problem. –  Robin Kothari Apr 12 '14 at 3:09
Maybe I should have said 'example of a simple problem' instead :). –  Suresh Venkat Apr 12 '14 at 18:15

Meyer auf der Heide described a non uniform family of linear decision trees for Subset Sum with depth $O(n^4\log n)$. A similar result can be deived from a later algorithm of Meiser for point location in hyperplane arrangements. Of course the problem is NP-hard.

-
If I wanted to be REALLY PEDANTIC I'd point out that being NP-hard is not a firm lower bound. but that's a good example of the spirit of what I'm looking for. –  Suresh Venkat Apr 12 '14 at 3:09
Yeah, but we don't know how to prove firm lower bounds. –  JɛﬀE Apr 12 '14 at 14:05
@JɛﬀE Do you maybe know of a nice write up or exposition of this result? I find the original very hard to follow, some definitions are not clear at all to me. –  domotorp Apr 16 '14 at 15:05
At least the basic definitions are described in my paper on linear degeneracy problems. –  JɛﬀE Apr 16 '14 at 18:25

Here is an example of a trivial gap between decision-tree and algorithmic complexity. The randomized decision tree complexity of local sorting (orienting a vertex-weighted graph) is $O(n\log(\frac{m+n}{n}))$ whereas the size of the input is $\Theta(n+m)$. Any algorithm needs to read the input, so there's a separation whenever $m=\omega(n)$. See Goddard, Kenyon, King, Schulman (SICOMP 1993).

-
Thanks, and welcome to Theoretical Computer Science ! –  Suresh Venkat Apr 15 '14 at 17:25
Let me disagree a bit. In the RAM model, we do not necessarily need to read the whole input. In the Turing machine model, there are many trivial problems that can be solved faster with a decision-tree (or on a RAM machine). Also see Robin's comment to the original question. –  domotorp Apr 15 '14 at 17:52