Workshop
Finding the homology of semialgebraic sets, certified by condition numbers
- Peter Buergisser (Technische Universität Berlin, Berlin, Germany)
Abstract
We begin by explaining an algorithm due to Niyogi, Smale and Weinberger for finding the homology of manifolds, in which the reach turns out to be the critical complexity parameter. We then go on to explain how the reach of a semialgebraic set can be bounded in terms of a condition number. Finally, we outline a numerically stable algorithm to compute the homology of basic semialgebraic sets that runs in single exponential time, outside a vanishingly small set of ill-conditioned input data.
The talk is mainly based on the joint paper with Felipe Cucker and Pierre Lairez (J ACM 2018).
