Die weit gestreuten Themen dieses Seminars reflektieren Interessen der Arbeitsgruppe. Das Seminar soll bei wenig Vorkenntnissen einen ersten Einstieg in diese Gebiete ermöglichen und die Möglichkeit bieten, die Arbeitsgruppe kennenzulernen.

Studierenden, die Interesse haben, eine Abschlussarbeit in dieser Fachgruppe zu schreiben, wird die Teilnahme am Seminar nahe gelegt.

Es handelt sich bei der Veranstaltung um ein Blockseminar. Der Raum MAR 4.062 befindet sich in der Marchstr. 23, der MA 313/314 direkt gegenüber von unseren Büros. Der Zeitplan für die Vorträge ist wie folgt:

Es wird einen zweiten Termin geben:

Einige der Themen sind aus dem brandneuen Buch "Condition: The Geometry of Numerical Algorithms" von Bürgisser und Cucker, das bei Springer noch diesen Herbst erscheint. Es im folgenden kurz mit Condition bezeichnet. Teilnehmern des Seminars werden einzelne, themenbezogene Kapitel des Buches kostenfrei zur Verfügung gestellt.

Es stehen die folgenden Themen zur Auswahl (bei Bedarf können noch weitere Themen hinzu kommen). Für weitere Details siehe unten.

Hier geht es um das effiziente Lösen dünn besetzter, linearer Gleichungssysteme.

In einer aufsehenerregenden Arbeit haben Spielman und Teng im Jahre 2003 gezeigt, dass sich symmetrische, diagonal dominante Gleichungssysteme in quasi-linearer Zeit approximativ lösen lassen. Dazu entwickelten diese Autoren eine fruchtbare Synthese von Methoden der Numerik, der Graphentheorie und der Theorie elektrischer Netzwerke (siehe Spielmans Hauptvortrag am ICM 2010). Diese ursprünglich sehr komplizierten Algorithmen sind nach und nach vereinfacht worden. Im Jahre 2013 haben Kelner et al. eine elegante und besonders einfache Variante dieser Algorithmen vorgestellt. Das Thema des Vortrags ist die Präsentation dieses Algorithmus.

Literatur:

• Kelner, Orecchia, Sidford amd Zhu - A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. STOC 2013, pp. 911-920.
• Lukas Noelke - Ein kombinatorisch/numerischer Algorithmus für symmetrische, diagonal dominante Gleichungssysteme. Bachelorarbeit, Uni Paderborn 2013.
• Nisheeth Vishnoi - Lx=b. Foundations and Trends in Theoretical Computer Science, Vol 8, No 1-2 2012.

Diese Formel besagt, dass das Volumen der Umgebung vom Radius $r$ eines konvexen Körpers im $\mathbb{R}^n$ eine Polynomfunktion in $r$ ist. Die Koeffizienten heissen (nach geeigneter Skalierung) die Quermasse des Körpers. Sie spielen eine wichtige Rolle in der Integralgeometrie.

Literatur:

• Klain und Rota - Introduction to geometric probability (Kap. 9). Lezioni Lincee, 1997.
• Schneider und Weil - Stochastic and Integral Geometry (Kap. 14). Springer, 2008.
• Abschnitt 4.2 aus Schneider, Convex bodies: The Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications.
• Hadwigers Klassiker "Vorlesungen Über Inhalt, Oberfläche und Isoperimetrie".

Dieser Vortrag soll ein Schnellkurs über Untermannigfaltigkeiten des $\mathbb R^n$ und Integration über Mannigfaltigkeiten sein. Ziel ist die Erklärung der Coarea Formel, welche eine Verallgemeinerung der Transformationsformel und Fubinis Theorem darstellt. Dieser Vortrag ist die Vorbereitung auf den Vortrag über Poincare's Formel.

Literatur:

• Abschnitte 2.1, 17.3 und Teile aus Abschnitt A.2 aus Condition.

Angenommen, $M$ ist eine feste Kurve in der $2$-dimensionalen Sphäre und $N$ ein zufällig gewählter Großkreis. Was ist die erwartete Anzahl Schnittpunkte von $M$ mit $N$? Das Ergebnis ist die Länge von $M$ geteilt durch $\pi$. Dieser Satz verallgemeinert auf höhere Dimensionen und soll im Vortrag bewiesen werden. (Es werden hierzu Grundkenntnisse der Analysis auf Mannigfaltigkeiten vorausgesetzt.)

Literatur:

• Abschnitt A.4.1 aus Condition

Für den allgemeinen Kontext siehe die Literatur bei "Quermasse und Steiners Formel"

Wie sensitiv hängt die Lösung eines linearen Optimierungsproblems von den Eingabedaten $d$ ab? Diese Frage lässt verschiedene Präzisierungen zu. Die Renegar-Cheung-Cucker (RCC) Konditionszahl $\kappa(d)$ ist ein quantitatives Mass für diese Abhängigkeit. Sie beschränkt auch die Komplexität, um eine Lösung zu berechnen. Im Vortrag soll diese Grösse definiert und ihre Eigenschaften besprochen werden.

Literatur:

• Kapitel 11 von Condition.

Dieser Vortrag schliesst an den vorigen an. Angenommen, wir haben eine zufällige Instanz eines linearen Optimierungsproblems (formalisiert durch Gausssche Verteilungen). Wie gross ist die Wahrscheinlichkeit, dass die RCC Konditionszahl $\kappa(d)$ grösser als die Schwelle $t$ ist? Was ist der Erwartungswert von $\log\kappa(d)$? Glücklicherweise ist dieser Erwartungwert klein, was in gewissem Sinne den Erfolg gewisser Algorithmen für LP erklärt.

Literatur:

• Kapitel 12 von Condition.

Die Gruppe $\operatorname{GL}(n,\mathbb C)$ operiert auf m-Tupeln $(v_1,\ldots,v_m)$ von Vektoren in $\mathbb C^n$ auf natürliche Weise. Gesucht sind polynomiale Funktionen in den Einträgen
der Vektoren $v_i$, die unter der Wirkung von $\operatorname{SL}(n,\mathbb C)$ invariant sind.
Die Determinante von $(v_{i_1},\ldots,v_{i_n})$ ist eine solche Invariante, wenn
$i_1,\ldots,i_n$ verschiedene Indizes in $\{1,2,\ldots,m\}$ bezeichnen. Der erste Fundamentalsatz der Invariantentheorie besagt, dass diese den Ring der Invarianten erzeugen.

Literatur:

• Fulton und Harris - Representation Theory (Appendix F). Springer, 1991.
• Sturmfels - Algorithms in Invariant Theory (Kapitel 3). Springer, 1993.

Für weiterführende Behandlungen siehe:

• Procesi - Lie Groups: An Approach through Invariants and Representations (Kapitel 11). Springer, 2007.

Die besten Algebraiker des 19. Jahrhundert haben zu diesem Thema beigetragen. Die Gruppe $\operatorname{SL}(2,\mathbb{C})$ operiert auf dem Vektorraum der binären Formen $f$ vom Grad $d$ in den Variablen $X,Y$ durch Substitution. Eine Invariante ist eine Polynomfunktion in den Koeffizienten von $f$, die invariant unter der Aktion von $\operatorname{SL}(2,\mathbb{C})$ ist. Betrachtet man auch die Abhängigkeit von $X$ und $Y$, so wird man zum Begriff der Kovariante geführt. Man möchte die Invarianten und Kovarianten verstehen.

Literatur:

• Sturmfels - Algorithms in Invariant Theory (Abschnitt 3.6). Springer, 1993.
• Procesi - Lie Groups: An Approach through Invariants and Representations (Kapitel 15). Springer, 2007.

Hinweis: Dieses Thema ist weitläufig und müsste in einem Gespäch genauer eingegrenzt werden.

Die Determinante $\det(X)$ ist ein homogenenes Polynom vom Grad $n$ in den $n^2$ Einträgen der Matrix $X=(x_{ij})$. Welche invertierbaren linearen Transformationen der Variablen lassen $\det(X)$ invariant? Diese Frage wurde bereits von Frobenius 1897 beantwortet. Es soll ein moderner Beweis dieses Satzes von Frobenius präsentiert werden. Als Vorlage liegt eine Beweisskizze von Landsberg vor,
bei der allerdings einige Lücken ausgefüllt werden müssten.    

Literatur:

• Landsberg - Geometric Complexity Theory: An Introduction for Geometers (Abschnitt 6.5).
• Frobenius - Uber die Darstellungen der endlichen Gruppen durch lineare Substitutionen. Sitzungsbericht Deutsche. Akad. Wiss. Berlin (1897), 994 - 1015.