### Applications of Ramsey's theorem to decision tree complexityApplications of Ramsey's theorem to decision tree complexity

Access Restriction
Subscribed

 Author Moran, Shlomo ♦ Snir, Marc ♦ Manber, Udi Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1985 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{k-bounded}$ if each query depends on at most $\textit{k}$ variables. No further assumptions on the type of queries are made. It is proved that one can replace the queries of any $\textit{k}-bounded$ decision tree that solves an order-invariant problem over a large enough input domain with $\textit{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 $\textit{k}-bounded$ decision trees, where $\textit{k}$ is a constant.An $&OHgr;(\textit{n}$ log $\textit{n})$ lower bound for the element uniqueness problem and several other problems for any $\textit{k}-bounded$ decision tree, such that $\textit{k}$ = $\textit{O}(\textit{nc})$ and $\textit{c}$ < 1/2 is proved. This lower bound is tight since there exist $\textit{n}1/2-bounded$ decision trees of complexity $\textit{O}(\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1985-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 32 Issue Number 4 Page Count 12 Starting Page 938 Ending Page 949

#### Open content in new tab

Source: ACM Digital Library