Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time
<|reference_start|>Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time: In this paper we describe an algorithm that takes as input a description of a semi-algebraic set $S \subset \R^k$, defined by a Boolean formula with atoms of the form $P > 0, P < 0, P=0$ for $P \in {\mathcal P} \subset \R[X_1,...,X_k],$ and outputs the first $\ell+1$ Betti numbers of $S$, $b_0(S),...,b_\ell(S).$ The complexity of the algorithm is $(sd)^{k^{O(\ell)}},$ where where $s = #({\mathcal P})$ and $d = \max_{P\in {\mathcal P}}{\rm deg}(P),$ which is singly exponential in $k$ for $\ell$ any fixed constant. Previously, singly exponential time algorithms were known only for computing the Euler-Poincar\'e characteristic, the zero-th and the first Betti numbers.<|reference_end|>
@article{basu2006computing,
    title={Computing the First Few Betti Numbers of Semi-algebraic Sets in Single
  Exponential Time},
    author={Saugata Basu},
    journal={arXiv preprint arXiv:math/0603263},
    year={2006},
    archivePrefix={arXiv},
    eprint={math/0603263},
    primaryClass={math.AG cs.SC}
}