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.