Page Content
Prof. Dr. Peter Bürgisser
- © Peter Bürgisser
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin
Büro
Raum MA 317 (3. OG)
Institut für Mathematik
Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.
Publikationen
| Citation key | PFJ-Computing-The-Homology-Of-Semialgebraic-Sets-I-Lax-Formulas |
|---|---|
| Author | Bürgisser, Peter and Cucker, Felipe and Tonelli-Cueto, Josué |
| Pages | 71–118 |
| Year | 2020 |
| DOI | 10.1007/s10208-019-09418-y |
| Journal | Foundations of Computational Mathematics |
| Volume | 20 |
| Number | 1 |
| Abstract | We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of closed semialgebraic sets given by Boolean formulas without negations over lax polynomial inequalities. 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. All previous algorithms solving this problem have doubly exponential complexity (and this is so for almost all input data). Our algorithm thus represents an exponential acceleration over state-of-the-art algorithms for all input data outside a set that vanishes exponentially fast. |
Zusatzinformationen / Extras
Quick Access:
Schnellnavigation zur Seite über Nummerneingabe
Auxiliary Functions
This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.