Kolloquium

In unserem Kolloquium algorithmische Mathematik und Komplexitätstheorie tragen Mitarbeiter und Gäste über aktuelle Themen ihrer Forschung vor.

Das Oberseminar findet dienstags von 10:15 bis etwa 11:45 Uhr im Raum MA 316 statt.

Speaker: Prof. Felipe Cucker, City University Hong Kong

We describe a randomized algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semi algebraic sets which works in weak exponential time. That is, out of a set of exponentially small measure in the product space of data and the random numbers generated by the algorithm, the cost of the algorithm is exponential in the size of the data. All algorithms previously  proposed for this problem have a complexity which is doubly exponential (and this is so for most of the data).

Speaker: Josué Tonelli Cueto

In this talk, we will introduce completely positive operators between psd cones and study their combinatorics, showing that they can be seen as continuous generalizations (in the sense of Klain and Rota) of the positive maps between non-negative and their combinatorics. Focusing on concrete examples, we will do this by showing how the continuous generalizations of the cycle existence digraph problem for digraphs and the perfect matching existence problem for bipartite graphs are solved (using continuous generalizations of the discrete setting) and how they can be applied, respectively, to obtain polynomial-time algorithms for the null-cone membership problem of simultaneous conjugation and left-right multiplication, and also for non-commutative Polynomial Identity Testing.