This is the video of the BMS Friday lecture by Felipe Cucker (CityU Hong Kong / Einstein Visiting Fellow TU Berlin) entitled "On the Homology of Semialgebraic Sets". The talk was given on June 29, 2018 at the BMS Loft at Urania.
In his talk, Cucker will 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 proposed for this problem have doubly exponential complexity (and this is so for almost all input data). This algorithm thus represents an exponential improvement over state-of-the-art algorithms for all input data outside of a set that vanishes exponentially fast.
For more information about BMS Fridays, visit our website at: math-berlin.de/academics/bms-fridays.