TR95-057 Authors: Dima Grigoriev, Marek Karpinski, A. C. Yao

Publication: 27th November 1995 13:59

Downloads: 2268

Keywords:

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.