Applications of Ramsey's Theorem to Decision Tree Complexity

Shlomo Moran, Marc Snir, Udi Manber

Research output: Contribution to journalArticlepeer-review

Abstract

Combinatorial techniques for extending lower bound results for decision trees to general types of queries are presented. Problems that are defined by simple inequalities between inputs, called order invariant problems, are considered. 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. An Ω(n log n) 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 is proved. This lower bound is tight since 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)
Pages (from-to)938-949
Number of pages12
JournalJournal of the ACM (JACM)
Volume32
Issue number4
DOIs
StatePublished - Oct 1 1985
Externally publishedYes

Keywords

  • Computational complexity
  • Ramsey's theorem
  • decision trees
  • lower bounds

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Applications of Ramsey's Theorem to Decision Tree Complexity'. Together they form a unique fingerprint.

Cite this