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.
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).
@cite_3
2049661027
The 3SUM problem is to decide, given a set of @math real numbers, whether any three sum to zero. It is widely conjectured that a trivial @math -time algorithm is optimal and over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies @math lower bounds on numerous problems in computational geometry and a variant of the conjecture implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures. In this paper we refute the 3SUM conjecture. We prove that the decision tree complexity of 3SUM is @math and give two subquadratic 3SUM algorithms, a deterministic one running in @math time and a randomized one running in @math time with high probability. Our results lead directly to improved bounds for @math -variate linear degeneracy testing for all odd @math . The problem is to decide, given a linear function @math and a set @math , whether @math . We show the decision tree complexity of this problem is @math . Finally, we give a subcubic algorithm for a generalization of the @math -product over real-valued matrices and apply it to the problem of finding zero-weight triangles in weighted graphs. We give a depth- @math decision tree for this problem, as well as an algorithm running in time @math .