Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-057 | 24th November 1995 00:00

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 algebraic decision trees for this problem.
The proof in fact gives an exponential lower bound on size
for the polyhedral decision problem MAX= of testing whether
the $j$-th number is the maximum among a list of $n$ real
numbers. Previously, except for linear decision trees, no
nontrivial lower bounds on the size of algebraic decision
trees for any familiar problems are known. We also establish
an interesting connection between our lower bound and the
maximum number of minimal cutsets for any rank-$d$ hypergraphs
on $n$ vertices.

ISSN 1433-8092 | Imprint