Lower bounds for algebraic decision trees

J. Michael Steele; Andrew C. Yao

doi:10.1016/0196-6774(82)90002-5

Lower bounds for algebraic decision trees

J. Michael Steele
, Andrew C. Yao

Faculty of Electronic and Information Engineering

Stanford University

Research output: Contribution to journal › Article › peer-review

93 Scopus citations

Abstract

A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an Ω(n²) bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.

Original language	English
Pages (from-to)	1-8
Number of pages	8
Journal	Journal of Algorithms
Volume	3
Issue number	1
DOIs	https://doi.org/10.1016/0196-6774(82)90002-5
State	Published - Mar 1982

Access to Document

10.1016/0196-6774(82)90002-5

Cite this

@article{1460bbc2469642b7b7a21c28b6857f59,

title = "Lower bounds for algebraic decision trees",

abstract = "A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an Ω(n2) bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.",

author = "\{Michael Steele\}, J. and Yao, \{Andrew C.\}",

year = "1982",

month = mar,

doi = "10.1016/0196-6774(82)90002-5",

language = "英语",

volume = "3",

pages = "1--8",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Lower bounds for algebraic decision trees

AU - Michael Steele, J.

AU - Yao, Andrew C.

PY - 1982/3

Y1 - 1982/3

N2 - A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an Ω(n2) bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.

AB - A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an Ω(n2) bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.

UR - https://www.scopus.com/pages/publications/0002943521

U2 - 10.1016/0196-6774(82)90002-5

DO - 10.1016/0196-6774(82)90002-5

M3 - 文章

AN - SCOPUS:0002943521

SN - 0196-6774

VL - 3

SP - 1

EP - 8

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

Lower bounds for algebraic decision trees

Abstract

Access to Document

Other files and links

Fingerprint

Cite this