Oberseminar Algebraische Komplexitätstheorie

Wintersemester 2010/2011

Prof. Dr. Peter Bürgisser



Vorträge

28.10.2010 14:15 E0.143 Symmetrische Determinantenrepräsentationen schwach schiefer Schaltkreise
Stefan Mengel

Welche multivariaten Polynome sich als Determinante einer Matrix polynomieller Größe darstellen lassen, ist eine klassische und gut verstandene Frage der algebraischen Komplexitätstheorie. Anders sieht es aus, wenn man zusätzlich fordert, dass die Matrix symmetrisch sein soll. In einem neuen Paper betrachten Grenet et al. diese Fragestellung. Sie zeigen, dass Determinanten symmetrischer Matrizen in Körpern mit Charakteristik verschieden von 2 dieselbe Ausdruckskraft haben wie die von asymmetrischen. Beide können genau die Polynome darstellen, die von schwach schiefen Schaltkreisen berechnet werden. Die Autoren betrachten auch die Situation in Charakteristik 2 und geben dabei eine fast vollständige Lösung einer Frage Bürgissers zur VNP-Vollständigkeit der partiellen Permanente.

In dem Vortrag werden die wesentlichen Inhalte aus dem Paper von Grenet et al. sowie eine Motivation der Betrachtungen aus der konvexen Geometrie präsentiert.

11.11.2010 14:15 P1.418 Geometrische Analyse des Konvexen Lösbarkeitsproblems
und
18.11.2010 14:15 P1.418 Dennis Amelunxen
und
25.11.2010 16:15 P1.418

Das Konvexe Lösbarkeitsproblem ist die Frage, ob ein Unterraum (gegeben als Kern oder Bild einer Matrix) einen (festen) konvexen Kegel schneidet, oder nicht. Bei entsprechender Wahl des Kegels ergeben sich z.B. LP (Lineare Programmierung), SOCP (Second-order Programmierung), SDP (Semidefinite Programmierung), welche ein breites Anwendungsgebiet in verschiedenen Bereichen der angewandten Mathematik bieten.

In den 2 Vorträgen soll eine Average-case Analyse des Konvexen Lösbarkeitsproblems vorgestellt werden, welche es in dieser Allgemeinheit bisher noch nicht gab. Evtl. wird auch auf Möglichkeiten der Modifizierung der Average-Case Analyse zu einer Geglätteten Analyse eingegangen. Der wesentliche Bestandteil der Argumentation ist die Einführung einer neuen Konditionszahl, die eine Analyse mittels geometrischer Methoden zulässt.

Die Vorträge beinhalten eine Vorstellung des Konvexen Lösbarkeitsproblems, verschiedene äquivalente Definitionen der neuen Konditionszahl, und die wichtigsten Zwischenschritte welche zu einer geometrischen Average-case Analyse führen. Technische Details werden nach Möglichkeit ausgespart.

16.12.2010 16:15 A5 Geometric Complexity Theory and Tensor Rank
und
13.1.2011 16:15 A5 Peter Bürgisser
und
20.1.2011 16:15 A5 Geometric complexity theory is an approach towards the fundamental lower bound problems in complexity theory based on algebraic geometry and representation theory. Originally, it has been proposed for the permanent versus determinant problem. Recently, the overall framework has been applied and further developed for the tensor rank problem (complexity of matrix multiplication). While no good lower bounds have been obtained so far with these methods, we have now a much clearer understanding of the mathematical difficulties to be overcome for advancing.