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 (Omega) (n squared) 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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1980
Accession Number
ADA091124

Entities

People

  • Andrew C. Yao
  • J. Michael Steele

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I
  • Human Systems

DTIC Thesaurus Topics

  • Algebraic Geometry
  • Algebraic Topology
  • Automata Theory
  • California
  • Computer Science
  • Computers
  • Contracts
  • Geometry
  • Inequalities
  • Military Research
  • Models
  • Numbers
  • Polynomials
  • Security
  • Theoretical Computer Science
  • Topology
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.