Can inputs in the decision tree model be computed?

Question

The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still unresolved by reading the article, are:

1. Can those functions be fed any values computed by the algorithm (including ones of asymptotically larger magnitudes) or just ones from the input array?
2. Do the coefficients in the linear decision trees have to be hard-coded? The article seems to indicate that there are as many of them as elements in the input (and even more, exponential in the maximum allowed degree $d$, for algebraic decision trees), which means they cannot be hard-coded. Or is the $n$ in this fragment different and actually only sums of some fixed number of terms, independent of the input length, are allowed?
3. Regarding point 1, does it make a difference, i.e. can some problems be solved asymptotically faster (or in less memory) when comparisons of differences (or linear combinations, or polynomial functions) of any intermediate computed numbers are allowed? If yes, does the answer change if the numbers fed to the functions can only be $𝛰$ of those in the input array?

Answer 1

A decision tree is a special kind of "program" which computes a function, usual from $\{0,1\}^n$ to $\{0,1\}$. Let's take an example from Wikipedia:

A decision tree is a binary tree. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\{0,1\}$. Each internal node has one child labeled $0$ (the left child in the diagram) and another child labeled $1$ (the right child in the diagram). The binary tree doesn't have to be complete as in the example above.

In order to evaluate the decision tree, you start from the root, evaluate the function written there, and descend to the left child or to the right child accordingly. You continue in this fashion until reaching a leaf, at which point you output the label written there.

The cost of a decision tree is its depth, or equivalently, the maximum number of edges in a root-to-leaf path.

The most common choice for the set $\mathcal{F}$ of allowed queries is $\{x_1,\ldots,x_n\}$. Linear decision trees are decision trees in which $\mathcal{F}$ consists of all linear threshold functions. Alegbraic decision trees of degree $d$ are decision trees in which $\mathcal{F}$ consists of all polynomial threshold functions of degree $d$.

Comparison-based algorithms can also be modeled by decision trees. Here the input is an array of length $n$, the output is a permutation of the positions of the array, and the allowed queries are comparisons.

Decision trees capture some properties of algorithms, and ignore other properties. They are most often used to prove lower bounds on algorithms solving a certain problem. For example, we can represent every comparison-based sorting algorithm as a decision tree. This representation completely ignores how difficult it is to decide what comparison to do next, and how difficult it is to generate the output given the results of past comparisons. Yet the model is useful, since it shows that every comparison-based sorting algorithm must make $\Omega(n\log n)$ comparisons in the worst case, and in particular, must have running time $\Omega(n\log n)$.

Kane, Lovett and Moran constructed linear decision trees of depth $\tilde{O}(n)$ solving the 3SUM problem. In contrast, the 3SUM conjecture states that no RAM-based algorithm for 3SUM runs in time substantially better than $O(n^2)$. This is one case in which the decision tree model isn't able to capture the hardness of a problem.

The main point here is that proving lower bounds on computation time is hard. The only lower bounds we know how to prove are in restricted models, or on a specific type of resource, such as queries in the decision tree model, or communication in the communication complexity model. These models abstract away computation but capture some pertinent properties which suffice for proving meaningful lower bounds in many cases.

We can now answer your questions one by one:

1. The decision tree model is really a family of models, parametrized by the set $\mathcal{F}$ of allowed queries. As a user of the decision tree model, you get to decide which queries you allow.

2. The decision tree model is a non-uniform model. You can use whatever functions from $\mathcal{F}$ that you wish. Unless stated specifically, there is no requirement that there be an efficient procedure that constructs the decision tree for inputs of given length.

3. The most common measure of complexity for decision trees is depth. Another measure of complexity sometimes used is size; in this case, we sometimes allow DAGs (known in this context as branching programs) rather than just (directed) trees. Enlarging the set $\mathcal{F}$ of allowed functions can reduce the complexity.

For the specific case of linear decision trees, it is known that arbitrary weights can be reduced to polynomial weights at the cost of increasing the depth by at most 1, see Goldmann and Karpinski, Simulating threshold circuits by majority circuits. (The models are not the same, but it seems likely that the conclusion still holds.)

Another example where comparing more complicated linear functions can make a large difference is 3SUM. The decision trees constructed by Kane, Lovett and Moran have sparsity 6, while an earlier lower bound of Ailon and Chazelle (cited in [KLM]) shows that sparsity 5 cannot achieve depth $\tilde{O}(n)$.