|
Logik in der Informatik
Prof. Dr. Martin Grohe |
|
Themen des Seminars sind in diesem Semester Expandergraphen.
Expandergraphen sind sehr stark zusammenhängende Graphen mit wenigen Kanten. Sie haben eine Reihe sehr seltsamer Eigenschaften, tatsächlich ist es nicht einfach, Expander überhaupt zu konstruieren.
Überraschenderweise haben Expander zahlreiche Anwendungen in der Informatik, beispielsweise kann man sie zum Derandomisieren randomisierter Algorithmen verwenden oder um schwer lösbare Eingabeinstanzen für SAT-Solver zu konstruieren. Einige der wichtigsten und tiefliegendsten Ergebnisse der theoretischen Informatik der letzten Jahre verwenden Expandergraphen.
Wir werden uns in diesem Seminar den Artikel Expander graphs and their applications von Hoory, Linial und Wigderson erarbeiten.
Freitags 9-11 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307.
S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Erscheint im Bulletin of the AMS.