Inhalt des Dokuments
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.
|Prof. Dr. Felipe Cucker||On the computation of the homology groups of basic
|Josué Tonelli Cueto ||Completely Positive Operators of Psd Cones, Their
(Continuous) Combinatorics and Applications to Null-Cone Membership
Problems and Polynomial Identity Testing.||06.06.2017|
On the computation of the homology groups of basic semialgebraic sets
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).
Completely Positive Operators of PSD Cones, Their (Continuous) Combinatorics and Applications to Nullcone Membership Problems and Polynomial Identity Testing
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.