We prove an exponential lower bound on the size of any fixed degree algebra
ic decision tree for solving MAX, the problem of finding the maximum of n r
eal numbers. This complements the n - 1 lower bound of [Rabin (1972)] on th
e depth of algebraic decision trees for this problem. The proof in fact giv
es an exponential lower bound on the size of the polyhedral decision proble
m MAX= for 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 probl
ems are known. We also establish an interesting connection between our lowe
r bound and the maximum number of minimal cutsets for any rank-d hypergraph
on n vertices.