| TR#: | CS0313 |
| Class: | CS |
| Title: | A Ramsey-Theorem Based Technique for Proving Lower Bounds on Decisions Trees |
| Authors: | Shlomo Moran |
| CS0313.pdf | |
| Abstract: | Let EU be tlie set of sequences (a1,...,an) in which ai!=aj for i!=j. Ramsey Theorem is used to show that in every decision tree T that accept EU, for every permutation pi there must be a computation path in T that 'compares' all pairs of consecutive elements of pi. This result is then used to prove a lower bound of OMEGA(nlogn) on decision trees that accepts EU and in which every query involves at most n^c input elements for some c<1/2. (If queries are allowed to use n^(1/2) input elements, then O(n) upper bound for this problem exists). In a forthcoming paper we generalize the technique presented here for proving lower bounds on other "order invariant" problems. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1984/CS/CS0313), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1984
To the main CS technical reports page