Computing the first few Betti numbers of semi-algebraic sets in single exponential time

DOI10.1016/j.jsc.2006.07.001zbMath1126.14065arXivmath/0603263OpenAlexW2163243521MaRDI QIDQ2457390

Saugata Basu

Publication date: 23 October 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0603263

zbMATH Keywords

spectral sequencesBetti numberssemi-algebraic setssingle exponential complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Algebraic topology (55-XX)

Related Items (16)

On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety ⋮ Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties ⋮ Computing Geometric Feature Sizes for Algebraic Manifolds ⋮ Persistent Homology of Semialgebraic Sets ⋮ Efficient simplicial replacement of semialgebraic sets ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time ⋮ Computing the first Betti number of a semi-algebraic set ⋮ Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets ⋮ On projections of semi-algebraic sets defined by few quadratic inequalities ⋮ Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ Effective de Rham cohomology — The general case ⋮ 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Weakly semialgebraic spaces
• 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
• Different bounds on the different Betti numbers of semi-algebraic sets
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Computing Roadmaps of General Semi-Algebraic Sets
• Computing the first Betti number and the connected components of 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
• Computer Algebra in Scientific Computing
• On the Betti Numbers of Real Varieties
• Algorithms in real algebraic geometry

This page was built for publication: Computing the first few Betti numbers of semi-algebraic sets in single exponential time