Monday, November 20, 2018
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
room MA 041
Lecture - 14:15
Deciding nonnegativity of real polynomials is a fundamental problem in real algebraic geometry and polynomial optimization, which has countless applications.
Since this problem is extremely hard, one usually restricts to sufficient conditions (certificates) for nonnegativity, which are easier to check. For example, since the 19th century the standard certificates for nonnegativity are sums of squares (SOS), which motivated Hilbert's 17th problem.
A maybe surprising fact is that both polynomial nonnegativity and nonnegativity certificates are closely related to different discrete structures such as polytopes and point configurations.
In this talk, I will give an introduction to nonnegativity of real polynomial with a focus on the combinatorial point of view.
Colloquium - 16:00
We report on the implementation of an algorithm for computing the set of all regular triangulations of finitely many points in Euclidean space. This algorithm, which we call down-flip reverse search, can be restricted, e.g., to computing full triangulations only; this case is particularly relevant for tropical geometry. Most importantly, down-flip reverse search allows for massive parallelization, i.e., it scales well even for many cores. Our implementation allows to compute the triangulations of much larger point sets than before.
This is joint work with Charles Jordan and Michael Joswig.