We describe a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of a basic semialgebraic set. The algorithm is numerically stable in the sense that the precision required to guarantee a correct output depends on the condition number of the data and it is polynomially small. Its running time also depends on this condition but it is bounded by a singly exponential bound on the size of the input out of a vanishingly small set of data. All algorithms previously proposed for this problem have a complexity which is doubly exponential (and this is so for almost all data).
This is joint work with Felipe Cucker and Pierre Lairez.