Computing the homology of basic semialgebraic sets in weak exponential time

Peter Bürgisser, Felipe Cucker, Pierre Lairez

We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semialgebraic sets which works in weak exponential time. That is,…