Finding the homology of semialgebraic sets, certified by condition numbers

  • Peter Buergisser (Technische Universität Berlin, Berlin, Germany)
E1 05 (Leibniz-Saal)


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).

01.07.19 04.07.19

Summer School on Randomness and Learning in Non-Linear Algebra

MPI für Mathematik in den Naturwissenschaften Leipzig (Leipzig) E1 05 (Leibniz-Saal)
Universität Leipzig (Leipzig) Felix-Klein-Hörsaal

Saskia Gutzschebauch

Max-Planck-Institut für Mathematik in den Naturwissenschaften Contact via Mail

Paul Breiding

Technische Universität Berlin

Jesus De Loera

University of California at Davis

Despina Stasi

Illinois Institute of Technology

Sonja Petrovic

Illinois Institute of Technology