direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

Computing the Homology of Semialgebraic Sets. II: General formulas
Citation key BCT-Computing-the-Homology-of-Semialgebraic-Sets-II:-General-Formulas
Author Peter Bürgisser and Felipe Cucker and Josué Tonelli-Cueto
Year 2019
Month 03
Abstract We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. This extends the previous work of the authors in arXiv:1807.06435 to arbitrary semialgebraic sets. All previous algorithms proposed for this problem have doubly exponential complexity (and this is so for almost all input data).
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.