Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time

Abstract

For any $\ell >0$, we present an algorithm which takes as input a semi-algebraic set, $S$, defined by $P_1\le 0,...,P_s\le 0$, where each $P_i\in \mathbb{R}[X_1,...,X_k]$ has degree $\le 2,$ and computes the top $\ell$ Betti numbers of $S$, $b_{k-1}(S),...,b_{k-\ell }(S),$ in polynomial time. The complexity of the algorithm, stated more precisely, is ${\sum }_{i=0}^{\ell +2}\left(\genfrac{}{}{0ex}{}{s}{i}\right)k^{2^{O(\min (\ell ,s))}}.$ For fixed $\ell$, the complexity of the algorithm can be expressed as $s^{\ell +2}{k}^{2^{O(\ell )}},$ which is polynomial in the input parameters $s$ and $k$. To our knowledge this is the first polynomial time algorithm for computing non-trivial topological invariants of semi-algebraic sets in ${\mathbb{R}}^k$ defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed $s$, we obtain by letting $\ell =k$, an algorithm for computing all the Betti numbers of $S$ whose complexity is $k^{2^{O(s)}}$.

Some more details added in Sections 6 and 7

References in corpus (1)

• Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

Cited by in corpus (7)

• Demonstration of Topological Data Analysis on a Quantum Processor
• 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
• The Persistent Topology of Optimal Transport Based Metric Thickenings
• Testing systems of real quadratic equations for approximate solutions
• Geodesic diameter of sets defined by few quadratic equations and inequalities