A new lower bound technique for decision trees

Fleischer, Rudolf

Local TagsRelease HistoryDetailsSummary

A new lower bound technique for decision trees

Fleischer, R.(1992). A new lower bound technique for decision trees (MPI-I-92-125). Saarbrücken: Max-Planck-Institut für Informatik.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B6FB-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-002E-25FD-9

Genre: Report

Files

show Files

hide Files

:

MPI-I-92-215__scan_ISTHPM7751_11032017-mitS8_mitOCR.pdf (Publisher version), 2MB

View Save

File Permalink:
https://hdl.handle.net/11858/00-001M-0000-002E-25FE-7

Name:
MPI-I-92-215__scan_ISTHPM7751_11032017-mitS8_mitOCR.pdf

Description:
-

OA-Status:

Visibility:
Public

MIME-Type / Checksum:
application/pdf / [MD5]

Technical Metadata:

View

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Fleischer, Rudolf¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

Abstract: 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.

Details

show

hide

Language(s): eng - English

Dates: Date issued: 1992

Publication Status: Issued

Pages: 21 p.

Publishing info: Saarbrücken : Max-Planck-Institut für Informatik

Table of Contents: -

Rev. Type: -

Identifiers: Report Nr.: MPI-I-92-125
BibTex Citekey: Fleischer_Report1992

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Research Report / Max-Planck-Institut für Informatik

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -