You are invited to our Monday Lecture & Colloquium on April 15th, 2019 at 14:15 h & 16:00 h at FU Berlin. Lecture: Monday, April 15th - 14:15 h =============================================== Kaie Kubjas (Sorbonne Université Paris): Nonnegative rank four boundaries =============================================== Abstract: Matrices of nonnegative rank at most r form a semialgebraic set. This semialgebraic set is understood for r=1,2,3. In this talk, I will recall what was previously known about this semialgebraic set and present recent results on the boundaries of the set of matrices of nonnegative rank at most four using notions from the rigidity theory of frameworks. These results are joint work with Robert Krone. In the nonnegative rank-3 case, all boundaries are trivial or consist of matrices that have only infinitesimally rigid factorizations. For arbitrary nonnegative rank, we give a necessary condition on zero entries of a nonnegative factorization for the factorization to be infinitesimally rigid, and we show that in the case of 5×5 matrices of nonnegative rank four, there exists an infinitesimally rigid realization for every zero pattern that satisfies this necessary condition. However, the nonnegative rank-4 case is much more complicated than the nonnegative rank-3 case, and there exist matrices on the boundary that have factorizations that are not infinitesimally rigid. We discuss two such examples. Coffee & Tea Break: Room 134 Colloquium: 16:00 h ====================================================================== Josué Tonelli-Cueto (Technische Universität Berlin): Condition meets Computational Geometry: The Plantinga-Vegter algorithm ====================================================================== Abstract: The Plantinga-Vegter algorithm is a subdivision algorithm that produces an isotopic approximation of implicit smooth curves in the plane (and also of surfaces in three-dimensional space). Despite remarkable practical success of the algorithm, little was known about its complexity. The only existing complexity analysis due to Burr, Gao and Tsigaridas provides worst-case bounds that are exponential both in the degree and the bit size of the input polynomial. Despite being tight, this worst-case bound doesn't explain why the algorithm is efficient in practice. In this talk, we show how condition numbers, combined with techniques from geometric functional analysis, help to solve this issue. This is joint work with Alperen A. Ergür and Felipe Cucker. =============================================================== Location: Room 005 - Ground Floor Freie Universität Berlin, Department of Computer Science Takustr. 9 14195 Berlin