Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time
| dc.creator | Basu, Saugata | |
| dc.date | 2006-03-10 | |
| dc.date.accessioned | 2026-07-07T07:06:47Z | |
| dc.date.available | 2026-07-07T07:06:47Z | |
| dc.description | 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é characteristic, the zero-th and the first Betti numbers. | |
| dc.identifier | https://arxiv.org/abs/math/0603263 | |
| dc.identifier | http://arxiv.org/abs/math/0603263 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/110150 | |
| dc.subject | Algebraic Geometry | |
| dc.subject | Symbolic Computation | |
| dc.subject | 14P10 ; 14P25 | |
| dc.title | Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time | |
| dc.type | text |