We completely characterise the complexity in the decision tree model of computing composite relations of the form h = g(f^1,...,f^n), where each relation f^i is boolean-valued. Immediate corollaries include a direct sum theorem for decision tree complexity and a tight characterisation of the decision tree complexity of iterated boolean functions.
@cite_3: A Direct Sum Theorem holds in a model of computation, when for every problem solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all relations. We also note that a near optimal Direct Sum Theorem holds for quantum decision trees for boolean functions.
In particular, Jain, Klauck and Santha have shown @cite_3 such a direct sum theorem for deterministic and randomised decision tree complexity. As discussed in @cite_3 , previous work had dismissed this question as uninteresting, but the proof is not immediate. In the deterministic case, the result of @cite_3 is proven by showing that, given a decision tree @math computing @math independent outputs, one can produce @math independent trees @math , one for each output, and lower bounding the depth of @math in terms of the depth of the trees @math . This approach does not seem suitable for proving a composition theorem, as given a tree computing @math , it is not necessarily possible to produce individual trees for @math . On the other hand, the composition theorem given here in fact implies a direct sum theorem for decision tree complexity (see Section for this and other corollaries).