ECCC-Report TR95-057https://eccc.weizmann.ac.il/report/1995/057Comments and Revisions published for TR95-057en-usMon, 27 Nov 1995 13:59:47 +0200
Paper TR95-057
| An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX |
Dima Grigoriev,
Marek Karpinski,
A. C. Yao
https://eccc.weizmann.ac.il/report/1995/057 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.
Mon, 27 Nov 1995 13:59:47 +0200https://eccc.weizmann.ac.il/report/1995/057