Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Fleischer, Rudolfdblp

BibTeX cite key*:

Fleischer_dectrees_1999

Title

Title*:

Decision trees: old and new results

Journal

Journal Title*:

Information and computation
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Academic Press
Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

152
Number:


Publishing Date:

1999

Pages*:

44-61
Number of
VG Pages:

39

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

In this paper, we prove two general lower bounds for algebraic
decision trees which test membership in a set $S\subseteq R^n$ which is
defined by linear inequalities.
Let $rank(S)$ be
the maximal dimension of a linear subspace contained in the closure of
$S$ {in the Euclidean topology}.

First we show that any decision tree for $S$ which uses
products of linear functions (we call such functions
{\em mlf-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 mlf-functions are not really more powerful
than simple comparisons between the input variables when
computing the largest $k$ out of $n$ elements.
Yao proved this result in the special case when
products of at most two linear functions are allowed.
Out proof also shows that any decision tree for this problem
must have exponential size.

Using the same methods, we can give an
alternative proof of Rabin's Theorem, namely
that the depth of any decision tree for $S$ using arbitrary
analytic functions is at least $n-rank(S)$.

URL for the Abstract:


Categories,
Keywords:

decision tree, lower bound

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:

@ARTICLE{Fleischer_dectrees_1999,
AUTHOR = {Fleischer, Rudolf},
 TITLE = {Decision trees: old and new results},
 JOURNAL = {Information and computation},
 PUBLISHER = {Academic Press},
 YEAR = {1999},
 VOLUME = {152},
 PAGES = {44--61},
}

Entry last modified by Rudolf Fleischer, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rudolf Fleischer		Created
03/22/2000 22:49:34
Revision
0.



Editor
Rudolf Fleischer



Edit Date
22/03/2000 22:49:34