Baisc semialgebraic sets are the parts of $\mathbb{R}^n$ that are defined by the conjunction of polynomial inequalities. They may have very different shapes and homology is a prominent tool to describe them. Nevertheless, the computation of the homology is challenging. So far, only double exponential complexity algorithms are known, with respect to the number of variables. That is, we can compute the homology of a semialgebraic set defined by $s$ polynomial equations and inequalities of degree $D$ in $n$ variables in $(sD)^{2^{O(n)}}$.

In “Computing the homology of basic semialgebraic sets in weak exponential time”, we design a numerical algorithm for this problem and we show that its complexity is $\big( (s+n)D / \delta \big)^{O(n^2)}$ where $\delta$ is related to the distance of the input equations to numerically ill-posed problems (which happens when infinitesimal pertubations of the input problem cause topological modifications). Furthermore, we provide probabilistic analysis of this complexity.

The method is to approximate the semialgebraic set with a cloud of points. If the cloud is close enough to the set and dense enough, then it allows to recover all the relevant information about the topology of the set.