Publication Details
Title: An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX
Author: D. Grigoriev, M. Karpinski, and A. C. Yao
Group: ICSI Technical Reports
Date: November 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-066.pdf
Overview:
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 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. Keywords: Lower Bounds, Algebraic Decision Trees, MAX Problem, Selection Problems, Hypergraphs, Minimal Cutsets
Bibliographic Information:
ICSI Technical Report TR-95-066
Bibliographic Reference:
D. Grigoriev, M. Karpinski, and A. C. Yao. An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX. ICSI Technical Report TR-95-066, November 1995
Author: D. Grigoriev, M. Karpinski, and A. C. Yao
Group: ICSI Technical Reports
Date: November 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-066.pdf
Overview:
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 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. Keywords: Lower Bounds, Algebraic Decision Trees, MAX Problem, Selection Problems, Hypergraphs, Minimal Cutsets
Bibliographic Information:
ICSI Technical Report TR-95-066
Bibliographic Reference:
D. Grigoriev, M. Karpinski, and A. C. Yao. An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX. ICSI Technical Report TR-95-066, November 1995