Lower bounds for algebraic decision trees

Journal of AlgorithmsPublished 1 March 1982

John Steele, Andrew Chi-Chih Yao

Citations152

TL;DR

A topological method is given for obtaining lower bounds for the height of algebraic decision trees and an Ω(n2) bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear 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.

Keywords

Computer ScienceEngineering

Proceedings of the American Mathematical SocietyOn the Betti numbers of real varieties

485 Citations1964John Milnor

Journal of the ACMA Lower Bound to Finding Convex Hulls

156 Citations1981Andrew Chi-Chih Yao

It is shown that any algorithm in the quadratic decision-tree model must make cn log n tests for some input.

View PDF

Journal of Computer and System SciencesOn the complexity of computations under varying sets of primitives

119 Citations1979David Dobkin, Richard J. Lipton

The goal of the current research is the study of lower bounds on the complexity of a set of searching problems under various restrictions on the nature of the primitive operation used to determine each branch in a search tree.

Journal of Computer and System SciencesProving simultaneous positivity of linear forms

77 Citations1972Michael O. Rabin

The notion of a complete proof for simultaneousPositivity is developed and it is shown that under certain natural conditions, proofs for the simultaneous positivity of m forms will always require m steps.

SIAM Journal on ComputingOn the Polyhedral Decision Problem

42 Citations1980Andrew Chi-Chih Yao, Ronald L. Rivest

A general lower bound to the complexity of polyhedra with abundant faces is given, showing that $\frac{1}{2}\log _2 f_s $ linear comparisons are needed in the worst case, for any polyhedron with $f_s$s-dimensional faces.

Computing the maximum and the median

19 Citations1971Edward M. Reingold

The new results are: (a) the maximum of a set of n integers cannot be computed in fewer than n-1 comparisons if comparisons of only linear functions of the integers are permitted, but the maximum can be compute in log2 n comparisons.

American Mathematical MonthlyOn the Division of the Plane by Lines

17 Citations1978John E. Wetzel

Journal of Computer and System SciencesA nonlinear lower bound on linear search tree programs for solving knapsack problems

13 Citations1976David Dobkin

By the method of region counting, a lower bound of n log"2nn queries is obtained onlinear search tree programs which solve the n-dimensional knapsack problem.