TU Berlin

Fachgebiet Algorithmische AlgebraKolloquium (Oberseminar)

Inhalt des Dokuments

zur Navigation


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.


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.

In principle, there will be two talks. This is part of my Master Thesis under the supervision of P. Bürgisser, based mainly in the recent work of Garg, Gurvits, Oliveira and Widgerson and of Ivanyos, Qiao and Subranmanyam among others.



Schnellnavigation zur Seite über Nummerneingabe