TY - GEN

T1 - APPLICATIONS OF RAMSEY'S THEOREM TO DECISION TREES COMPLEXITY.

AU - Moran, Shlomo

AU - Snir, Marc

AU - Manber, Udi

PY - 1984

Y1 - 1984

N2 - Combinatorial techniques for extending lower bounds results for decision trees to general types of queries are presented. The authors consider problems, which they 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. No further assumptions on the type of queries are made. It is proved that one 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-bounded decision trees, where k is a constant. Also proved is an OMEGA (n log n) lower bound for the element uniqueness problem and several other problems for any k-bounded decision tree, such that k equals O(n**c ) and c greater than 1/2. This lower bound is tight since there exist n**1 **/ **2 -bounded decision trees of complexity O(n) that solve the element uniqueness problem. All the lower bounds mentioned above are shown to hold for nondeterministic and probabilistic decision trees as well.

AB - Combinatorial techniques for extending lower bounds results for decision trees to general types of queries are presented. The authors consider problems, which they 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. No further assumptions on the type of queries are made. It is proved that one 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-bounded decision trees, where k is a constant. Also proved is an OMEGA (n log n) lower bound for the element uniqueness problem and several other problems for any k-bounded decision tree, such that k equals O(n**c ) and c greater than 1/2. This lower bound is tight since there exist n**1 **/ **2 -bounded decision trees of complexity O(n) that solve the element uniqueness problem. All the lower bounds mentioned above are shown to hold for nondeterministic and probabilistic decision trees as well.

UR - http://www.scopus.com/inward/record.url?scp=0021562127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021562127&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0021562127

SN - 081860591X

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 332

EP - 337

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -