Oberseminar Algebraische Komplexitätstheorie

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.

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.