The title is a little misleading: but hopefully the question isn't:Grnlund 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 ? 
Provable gaps between decision tree complexity and true complexity
cc.complexity theory;machine models;decision trees
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.