Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A new lower bound technique for decision trees

Fleischer, Rudolf

MPI-I-92-125. April 1992, 21 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
In this paper, we prove two general lower bounds for algebraic
decision trees which test membership in a set $S\subseteq\Re^n$ which is
defined by linear inequalities.
Let $rank(S)$ be
the maximal dimension of a linear subspace contained in the closure of
% \endgraf
First we prove that any decision tree which uses multilinear
functions (i.e.~arbitrary
products of linear functions) must have depth
at least $n-rank(S)$.
This solves an open question raised by A.C.~Yao
and can be used to show
that multilinear functions are not really more powerful
than simple comparisons between the input variables when
computing the largest $k$ elements of $n$ given numbers.
Yao could only prove this result in the special case when
products of at most two linear functions are used.
Our proof is based on a dimension argument.
It seems to be the first time that such an approach
yields good lower bounds for nonlinear decision trees.
% \endgraf
Surprisingly, we can use the same methods to give an
alternative proof for Rabin's fundamental Theorem,
namely that the depth of any decision tree using arbitrary
analytic functions is at least $n-rank(S)$.
Since we show that Rabin's original proof is incorrect,
our proof of Rabin's Theorem is not only the first correct one
but also generalizes the Theorem to a wider class of functions.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Fleischer, Rudolf},
  TITLE = {A new lower bound technique for decision trees},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-92-125},
  MONTH = {April},
  YEAR = {1992},
  ISSN = {0946-011X},