I recently discovered a quadratic lower bound on the complexity of a problem in the decision tree model, and I wonder whether this result could be partially generalized to the random access machine model. By partially, I mean a generalization to RAM programs with a certain time/space tradeoff. For instance, I'd like to show that my problem cannot be solved by a linear-time and -space RAM program.
A.M. Ben-Amram and Z. Galil proved in this paper that a RAM program running in time $t$ and space $s$ can be simulated in $O(t \, \log s)$ time on a pointer machine. Do we know similar results which could be applied to decision trees?
Alternatively, is it possible to simulate a RAM program running in space $s$ with a decision tree of degree $s$? (intuitively, indirect addressing could be simulated using nodes of degree $\leq s$)