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
First we prove that any decision tree which uses multilinear
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.
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):|
|Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView|