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 2950902318 1523387560 2609730020
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 . We prove that for any decision tree calculating a boolean function @math , [ [f] i=1 ^n (f), ] where @math is the probability that the @math th input variable is read and @math is the influence of the @math th variable on @math . The variance, influence and probability are taken with respect to an arbitrary product measure on @math . It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced boolean function with a decision tree of depth @math has a variable with influence at least @math . The only previous nontrivial lower bound known was @math . Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with non-boolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least @math , where @math is the number of vertices and @math is the critical threshold probability. This supersedes the milestone @math bound of Hajnal and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson. 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. The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as @math , etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical @math -Coloring . A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the @math -level Hierarchical @math -Coloring problem is @math , for @math . The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized @math -time algorithm solving the LCL can be transformed into a deterministic @math -time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges @math --- @math or @math --- @math . 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in @math time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be @math and @math .