Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR95-057 | 24th November 1995 00:00

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

TR95-057
Authors: Dima Grigoriev, Marek Karpinski, A. C. Yao
Publication: 27th November 1995 13:59
Keywords:

Abstract:

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