Applications of ramsey's theorem to decision trees complexity

Shlomo Moran, Marc Snir, Udi Manber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PublisherIEEE Computer Society
Pages332-337
Number of pages6
ISBN (Electronic)081860591X
StatePublished - 1984
Externally publishedYes
Event25th Annual Symposium on Foundations of Computer Science, FOCS 1984 - Singer Island, United States
Duration: Oct 24 1984Oct 26 1984

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1984-October
ISSN (Print)0272-5428

Conference

Conference25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Country/TerritoryUnited States
CitySinger Island
Period10/24/8410/26/84

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Applications of ramsey's theorem to decision trees complexity'. Together they form a unique fingerprint.

Cite this