Computing the first Betti number of a semi-algebraic set

DOI10.1007/s10208-007-9001-1zbMath1142.14036OpenAlexW2012678207MaRDI QIDQ937278

Richard Pollack, Marie-Françoise Roy, Saugata Basu

Publication date: 20 August 2008

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-007-9001-1

zbMATH Keywords

complexityalgorithmBetti numberssemi-algebraic setssingly exponential time

Mathematics Subject Classification ID

Computational aspects of higher-dimensional varieties (14Q15) Semialgebraic sets and related spaces (14P10) Topology of real algebraic varieties (14P25)

Related Items

Persistent Homology of Semialgebraic Sets, Efficient simplicial replacement of semialgebraic sets, The persistent topology of optimal transport based metric thickenings, Unnamed Item, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets, Computing the homology of real projective sets, Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials, Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials, Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets, A complexity theory of constructible functions and sheaves

Cites Work

• Unnamed Item
• Unnamed Item
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Counting connected components of a semialgebraic set in subexponential time
• On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets
• Construction of roadmaps in semi-algebraic sets
• Description of the connected components of a semialgebraic set in single exponential time
• Different bounds on the different Betti numbers of semi-algebraic sets
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Computing Roadmaps of General Semi-Algebraic Sets
• Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings
• On the combinatorial and algebraic complexity of quantifier elimination
• Computing roadmaps of semi-algebraic sets on a variety
• On the Betti Numbers of Real Varieties