# MPI-I-92-125

## 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

$S$.

% \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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 88 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-125

**BibTeX**
`@TECHREPORT{``Fleischer92b``,`

` 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},`

`}`