Article

Lower bounds for algebraic computation trees with integer inputs

Author:

A. C. -C. YaoAuthors Info & Claims

SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

Pages 308 - 313

https://doi.org/10.1109/SFCS.1989.63495

Published: 30 October 1989 Publication History

Publisher Site

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.

Cited By

View all

Bilardi GEkanadham KPattnaik PGiorgi RBecchi MPalumbo F(2017)Optimal On-Line Computation of Stack Distances for MIN and OPTProceedings of the Computing Frontiers Conference10.1145/3075564.3075571(237-246)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1145/3075564.3075571
Gawrychowski P(2011)Pattern matching in lempel-Ziv compressed stringsProceedings of the 19th European conference on Algorithms10.5555/2040572.2040619(421-432)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040619
Hurtado FMora MRamos PSeara C(2004)Separability by two lines and by nearly straight polygonal chainsDiscrete Applied Mathematics10.1016/j.dam.2003.11.014144:1-2(110-122)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1016/j.dam.2003.11.014
Show More Cited By

Lower bounds for algebraic computation trees with integer inputs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Algebraic computation trees in characteristic p>0
SFCS '94: Proceedings of the 35th Annual Symposium on Foundations of Computer Science

We provide a simple and powerful combinatorial method for proving lower bounds for algebraic computation trees over algebraically closed fields of characteristic p>0. We apply our method to prove, for example, an /spl Omega/(n log n) lower bound for the ...
Topological Lower Bounds on Algebraic Random Access Machines

We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations $\{+,-,\times,/\}$, as well as RAMs that use the operations $\{+,-,\times,\lfloor\;\rfloor\}$. We do it by ...
New Bounds and Constructions for Granular Media Coding
Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert-Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

October 1989

586 pages

ISBN:0818619821

Publisher

IEEE Computer Society

United States

Publication History

Published: 30 October 1989

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bilardi GEkanadham KPattnaik PGiorgi RBecchi MPalumbo F(2017)Optimal On-Line Computation of Stack Distances for MIN and OPTProceedings of the Computing Frontiers Conference10.1145/3075564.3075571(237-246)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1145/3075564.3075571
Gawrychowski P(2011)Pattern matching in lempel-Ziv compressed stringsProceedings of the 19th European conference on Algorithms10.5555/2040572.2040619(421-432)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040619
Hurtado FMora MRamos PSeara C(2004)Separability by two lines and by nearly straight polygonal chainsDiscrete Applied Mathematics10.1016/j.dam.2003.11.014144:1-2(110-122)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1016/j.dam.2003.11.014
Mulmuley KLeighton FShor P(1997)Is there an algebraic proof for P ≠ NC? (extended abstract)Proceedings of the twenty-ninth annual ACM symposium on Theory of computing10.1145/258533.258586(210-219)Online publication date: 4-May-1997
https://dl.acm.org/doi/10.1145/258533.258586
Schuierer SWood D(1995)Staircase visibility and computation of kernelsAlgorithmica10.1007/BF0130037114:1(1-26)Online publication date: 1-Jul-1995
https://dl.acm.org/doi/10.1007/BF01300371
Mulmuley KLeighton FGoodrich M(1994)Lower bounds for parallel linear programming and other problemsProceedings of the twenty-sixth annual ACM symposium on Theory of Computing10.1145/195058.195413(603-614)Online publication date: 23-May-1994
https://dl.acm.org/doi/10.1145/195058.195413
Zhang WWen ZHwang CBrice R(1991)Efficient parallel algorithms for some integer problemsProceedings of the 19th annual conference on Computer Science10.1145/327164.327169(11-20)Online publication date: 1-Apr-1991
https://dl.acm.org/doi/10.1145/327164.327169

Abstract

Cited By

Recommendations

Algebraic computation trees in characteristic p>0

Topological Lower Bounds on Algebraic Random Access Machines

New Bounds and Constructions for Granular Media Coding

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations