Complexity lower bound: the gap between decision trees and RAMs

Question

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$)

Answer 1

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.)

Answer 2

The natural model related to decision trees that simulates RAMs without loss 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 on a RAM.) Is that the form of your problem?

You seem to suggest that you are using the # of outputs to try to get a larger lower bound. However, even with this you also can compute any function with height = # inputs and space = # input bits. (Read and remember the input, and output all the values required at each leaf node. It is usual to allow multiple outputs at a single node.)