Technical Report CS0345

Title: Applications of Ramsey's Theorem to Decision Trees Complexity
Authors: S. Moran , M. Snir and U. Manber
Abstract: Combinatorial techniques for extending lower bounds results for decision trees to general types of quiries are presented. We consider problems, which we call order invariant, that are defined by simple inequalities between inputs. A decision tree is called k-bounded if each query depends on at most k variables. We make no further assumptions on the type of queries. We prove that we can replace the queries of any k-bounded decision tree that solves an order invariant problem over a large enough input domain with k -bounded queries whose outcome depends only on the relative order of the inputs. As a consequence, all existing lower bounds for comparison based algorithms are valid for general k-bouded decision trees, where k is a constant. We also prove all Omega(n*logn) lower bound for the element uniqueness problem and several other problems, for any k-bounded decison tree, such that k=O(n^C) and c<1/2. This lower bound is tight since that there exist n^(1/2)-bounded decision trees of complexity O(n) that solve the element uniqueness problem. All the lower pounds menitioned above are shown to bold for nondeterministic and probabilistic decision trees as well.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1984
To the main CS technical reports page

Computer science department, Technion