Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1995 Copyright 1995 University of Bonn, Department of Computer Science, Abt. V
85143

A Lower Bound on the Size of Algebraic Decision Trees for the MAX Problem
Dima Grigoriev, Marek Karpinski, Andrew Yao
[Download PostScript] [Download PDF]

We prove an exponential lower bound on the size of (ternary) algebraic decision trees for the MAX Problem of finding maximum of n real numbers. This complements $n-1$ lower bound (cf\@. M. O. Rabin \cite{R72}) on the depth of algebraic decision trees for this problem. The method yields also for the first time a lower size bound for a polyhedral decision problem MAX= of testing whether the $ith$ number is the maximum among a list of n real numbers, and gives the first nonlinear size lower bound on algebraic decision trees for the selection problems.

Last Change: 08/18/99 at 13:00:38
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V