Inhalt des Dokuments
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.
Terminplan
Vortragender | Titel | Datum | Zeit |
---|---|---|---|
Prof. Dr. Felipe Cucker | On the computation of the homology groups of basic semialgebraic sets | 02.05.2017 | 1015-1145 |
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 13.06.2017 | 1015-1145 |
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.