Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time
<|reference_start|>Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time: For any $\ell > 0$, we present an algorithm which takes as input a semi-algebraic set, $S$, defined by $P_1 \leq 0,...,P_s \leq 0$, where each $P_i \in \R[X_1,...,X_k]$ has degree $\leq 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} {s \choose i} 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 $\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)}}$.<|reference_end|>
@article{basu2006computing,
    title={Computing the Top Betti Numbers of Semi-algebraic Sets Defined by
  Quadratic Inequalities in Polynomial Time},
    author={Saugata Basu},
    journal={arXiv preprint arXiv:math/0603262},
    year={2006},
    doi={10.1007/s10208-005-0208-8},
    archivePrefix={arXiv},
    eprint={math/0603262},
    primaryClass={math.AG cs.CC math.LO}
}