Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOWER BOUNDS ALGEBRAIC DECISION TREES:
Reports tagged with Lower Bounds Algebraic Decision Trees:
TR95-057 | 24th November 1995
Dima Grigoriev, Marek Karpinski, A. C. Yao

An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

We prove an exponential lower bound on the size of any
fixed-degree algebraic decision tree for solving MAX, the
problem of finding the maximum of $n$ real numbers. This
complements the $n-1$ lower bound of Rabin \cite{R72} on
the depth of ... more >>>




ISSN 1433-8092 | Imprint