Lower bounds for arithmetic networks. II: Sum of Betti numbers

DOI10.1007/BF01613615zbMath0844.68069OpenAlexW2077846676MaRDI QIDQ1908901

J. E. Morais, José Luis Montaña, Luis Miguel Pardo

Publication date: 5 May 1996

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01613615

zbMATH Keywords

parallel complexitysemialgebraic setsmembership problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

Lower bounds for diophantine approximations, Nearly sharp complexity bounds for multiprocessor algebraic computations, Bounding the equivariant Betti numbers of symmetric semi-algebraic sets, Semi-algebraic decision complexity, the real spectrum, and degree, Topological lower bounds for arithmetic networks, Lower bound on testing membership to a polyhedron by algebraic decision and computation trees, Topological complexity of the relative closure of a semi-Pfaffian couple, Kronecker's and Newton's approaches to solving: a first comparison, A complexity theory of constructible functions and sheaves

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Definability and fast quantifier elimination in algebraically closed fields
• On the topology of algorithms. I
• On the complexity of computations under varying sets of primitives
• Complexity of deciding Tarski algebra
• Lower bounds for arithmetic networks
• Lower bounds for algebraic decision trees
• TIME BOUNDED COMPUTATIONS OVER THE REALS
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
• On the Betti Numbers of Real Varieties