[Facets-of-complexity] Monday Lecture & Colloquium - April 15, 2019 at FU Berlin

[Günter Rote <rote@inf.fu-berlin.de>]

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