Complexity lower bound: the gap between decision trees and RAMs 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$)
The natural model related to decision trees that can simulates RAMs is the branching program.  Basically, it is a decision tree with common subtrees coalesced yielding a DAG.   Time T and space S on a RAM can be simulated in height T and size 2^S on a branching program.  (You might need to use multi-way branching.)

For decision problems, it is clear that any decision tree only needs height = # inputs and space=total # of bits in the input.  Note that with multi-way branching one might have the # bits in the input larger than the usual measure of the # of inputs (e.g. n pointers each taking log n bits.)    For such problems with nlog n total input bits one can prove that certain problems cannot be solved in time O(n) and space=O(n) bits.  Is that the form of you problem?

You seem to suggest that you are using the # of outputs to try to get a larger lower bound.  It is usual for multi-output problems to allow many outputs along a single edge rather than at leaf nodes (see, for example, Borodin-Cook's 1982 paper on sorting lower bounds).  However, even without this assumption, one also can compute any function with height = # inputs and space = # input bits.  (Read and remember the input, and output all the values at each leaf node.)