TY - GEN
T1 - Applications of ramsey's theorem to decision trees complexity
AU - Moran, Shlomo
AU - Snir, Marc
AU - Manber, Udi
N1 - Funding Information:
* Supported in part by the National Science Foundation under Grant
Funding Information:
Supported in part by the National Science Foundation under Grant MCS83-03134.
Publisher Copyright:
© 1984 IEEE.
PY - 1984
Y1 - 1984
N2 - Combinatorial techniques for extending lower bounds results for decision trees to general types of queries 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-bounded decision trees, where k is a constant. We also prove an Ωl(n logn) lower bound for the element uniqueness problem and several other problems for any k-bounded decision tree, such that k = O(nc) and c<1/2. This lower bound is tight since that there exist n1/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. 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-bounded decision trees, where k is a constant. We also prove an Ωl(n logn) lower bound for the element uniqueness problem and several other problems for any k-bounded decision tree, such that k = O(nc) and c<1/2. This lower bound is tight since that there exist n1/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=85115235100&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115235100&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85115235100
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 332
EP - 337
BT - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PB - IEEE Computer Society
T2 - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Y2 - 24 October 1984 through 26 October 1984
ER -