Lower bounds for algebraic computation trees with integer inputs
Author:
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 308-313
Abstract
A proof is given of a general theorem showing that for certain sets W a certain topological lower bound is valid in the algebraic computation tree model, even if the inputs are restricted to be integers. The theorem can be used to prove tight lower bounds for the integral-constrained form of many basic problems, such as element distinctness, set disjointness, and finding the convex hull. Through further transformations it leads to lower bounds for problems such as the integer max gap and closest pair of a simple polygon. The proof involves a nontrivial extension of the Milnor-Thom techniques for finding upper bounds on the Betti numbers of algebraic varieties.Keywords
This publication has 14 references indexed in Scilit:
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple PolygonSIAM Journal on Computing, 1988
- Lower bounds for integer greatest common divisor computations1988
- Obtaining lower bounds using artificial componentsInformation Processing Letters, 1987
- Finding the convex hull of a simple polygonJournal of Algorithms, 1983
- The Computational Complexity of Continued FractionsSIAM Journal on Computing, 1983
- Lower bounds for algebraic computation trees1983
- On Parallel Computation for the Knapsack ProblemJournal of the ACM, 1982
- Lower bounds for algebraic decision treesJournal of Algorithms, 1982
- A lower bound of 12n2 on linear search programs for the Knapsack problemJournal of Computer and System Sciences, 1978
- On the Betti Numbers of Real VarietiesProceedings of the American Mathematical Society, 1964