Felipe Cucker (City U of Hong Kong/EVF TU Berlin)
Friday, June 29, 2018 - 14:15
Urania, BMS Loft
An der Urania 17, 10787 Berlin
BMS Friday colloquium
Berlin Mathematical School
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.

Felipe Cucker is a Uruguayan mathematician and Chair Professor at the City University of Hong Kong. He is also an Einstein Visiting Fellow at the TU Berlin. Cucker got his PhD jointly from U Rennes in France and U Cantabria in Spain in 1986. His research interests lie in the areas of complexity and computation. Cucker was on the board of directors of the Society for the Foundations of Computational Mathematics (FoCM) from its creation in 1995 until 2017. He was also its chairman (2008 - 2011) and managing editor of its journal (2011 - 2017). In 2005, he was made a foreign member of the Barcelona Royal Academy of Art and Sciences.
submitted by Fagel (fagel@math.tu-berlin.de)