Hauptseminar - Themenvorschläge
Das Thema des Hauptseminars sind randomisierte Algorithmen. Hier finden Sie eine Liste von Themenvorschlägen. Für zusätzliche Vorschläge bin ich offen
Emo Welzls Vorlesungsskript zum Thema SAT
Zu den SAT-Themen gibt es kein einheitliches Lehrbuch. Es gibt aber das hervorragende Vorlesungsskript von Emo Welzl.
Kargers Algorithmus. Ein Cut in einem ungerichteten Graphen $G = (V,E)$ ist eine Menge $S \subseteq V$ mit $S \ne \emptyset$ und $S \ne V$. Die Kapazität $c(S)$ des Cuts ist die Anzahl der Kanten zwischen $S$ und $V \setminus S$:
\begin{align*} c(S) := \left| \left\{ e \in E \ | \ |e \cap S| = 1 \right\}\right| \end{align*}Das Problem Minimum Cut fragt nach einem Cut $S$, der $c(S)$ minimiert. Je höher der Minimum Cut, desto "besser" sind die Knoten im Graphen verbunden. Der Minimum Cut ist also ein Maß für die "Verletzlichkeit" des Graphen. Kargers Algorithmus ist einfach und elegant: wähle eine Kante $\{u,v\}$ zufällig und verschmelze dann die Knoten $u$ und $v$ zu einem Meta-Knoten. Wiederhole diesen Schritt, bis nur noch zwei Meta-Knoten übrig sind. Diese Meta-Knoten entsprechen nun den Mengen $S$ und $V \setminus S$. Mit überraschend guter Wahrscheinlichkeit ist dies ein Min-Cut, so dass einfache Wiederholung Ihnen sehr wahrscheinlich einen Min-Cut liefert. Darüberhinaus kann man rekursive Verbesserungstricks anwenden, um die Laufzeit deutlich zu reduzieren.
Vorteile. Ein schöner, anschaulicher und einfach genialer Algorithmus. Ein Beispiel dafür, wie man mithilfe randomisierter Argumente interessante, nicht-randomisierte Aussagen beweisen kann (hier: ein ungerichteter Graphen kann höchstens $O(n^2)$ verschiedene Min-Cuts haben). Eignet sich gut für graphische Präsentationen mit vielen Abbildungen und Beispielen.
Nachteile. Eigentlich keine.
A random walk algorithm for 2-SAT. Hier sehen Sie eine Boolesche Formel in konjunktiver Normalform, kurz CNF:
\begin{align*} (x \vee \bar{y} \vee z) \wedge (\bar{x} \vee u \vee \bar{z} \vee w) \wedge \dots \end{align*}SAT ist das Problem, für so eine gegebene CNF-Formel eine erfüllende Belegung zu finden. SAT ist ein zentrales NP-vollständige Problem und ist höchstwahrscheinlich schwierig, d.h. es gibt wohl keinen effizienten Algorithmus für SAT. Eine prominente Ausnahme ist 2-SAT; dies ist SAT auf Formeln, in denen jede Klausel nur zwei Variable enthält, zum Beispiel also
\begin{align*} (x \vee y) \wedge (\bar{y} \vee u) \wedge (u \vee \bar{x}) \vee (\bar{x} \vee w) \wedge \dots \end{align*}Für 2-SAT sind mehrere effiziente Algorithmen bekannt. Besonders elegant ist der randomisierte Algorithmus von Papadimitriou. Man startet mit einer beliebigen Wahrheitsbelegung und wiederholt folgenden Schritt: nimm eine beliebige unerfüllte Klausel, wähle zufällig eine der beiden Variablen darin und ändere deren Wert. Wenn die Formel $F$ überhaupt eine erfüllende Belegung hat, dann findet dieser einfache Algorithmus nach durchschnittlich $O(n^2)$ eine.
Wenn es zeitlich passt, nehmen Sie noch Schönings Random-Walk-Algorithmus für $k$-SAT dazu. Das ist einer der bekanntesten Algorithmen für SAT und ist "fast geschenkt", wenn Sie den $2$-SAT-Algorithmus schon drangebracht haben. Die Analyse ist allerdings etwas anders, aber dennoch gut zu kennen.
Vorteile. Bei diesem Thema setzen Sie sich mit Random Walks auseinander, die ein grundlegendes Objekt in der Analye zufallsbasierter Prozesse darstellen. Für eine Seminarpräsentation eignet sich, dass Sie viel mit Abbildungen, Animationen und Beispielen arbeiten können.
Nachteil. Das Problem SAT ist als algorithmisches Problem eventuell neu und ungewohnt für Sie.
Der PPZ-Algorithmus für SAT. Dies ist ein weiterer randomisierter Algorithmus für $k$-SAT. Sie gehen die Variablen in zufälliger Reihenfolge durch und setzen Sie zufällig auf 0 oder 1, außer wenn Sie einer Klausel wie $(x)$ oder $(\bar{x})$ begegnen - in diesem Falle gibt es offensichtlich nur einen richtigen Wert. Die Analyse der Erfolgswahrscheinlichkeit ist äußerst interessant und verwendet wichtige Konzepte wie Indikatorvariablen, Erwartungswert und Konvexität.
Vorteile. Thema und Technik sind nicht nur für die Algorithmik wichtig, sondern auch für die Komplexitätstheorie. Das Thema ist von allen vorgeschlagenen am nächsten an der "richtigen" Forschung dran. Wenn Sie an Komplexitätstheorie interessiert sind oder mit dem Gedanken spielen, Ihre Bachelor-Arbeit in der theoretischen Informatik zu schreiben, ist es Ihr Thema.
Nachteile. Der PPZ-Algorithmus ist nicht effizient. Er hat exponentielle Laufzeit. Vielleicht haben Sie emotionale oder moralische Probleme, über exponentielle Algorithmen zu sprechen. Auch entfaltet das Thema sein ganzes Potential erst dann, wenn jemand Anderes das vorherige Thema (Ranndom Walk Algorithms for SAT) übernimmt.
Primzahl-Tests. Wie überprüft man, ob eine gegebene Zahl $r \in \mathbb{N}$ eine Primzahl ist? Man kann natürlich alle Teiler bis $\sqrt{r}$ durchprobieren, viel hilft das aber nicht: wenn $n$ die Anzahl der Stellen von $r$ ist (in Binärschreibweise), dann muss man immer noch $2^{n/2}$ Teiler durchprobieren. Können wir einen Primzahltest entwickeln, dessen Laufzeit polynomiell in $n$ ist? Das Lehrbuch Randomized Algorithms von Motwani und Raghawan erklärt ausführlich den sogenannten Miller-Rabin-Test, aber auch einfachere Algorithmen.
Vorteil. Primzahl-Tests sind ein Paradebeispiel für effiziente Algorithmen. Jeder sollte es einmal gesehen (und verstanden) haben. Das Material ist ein Klassiker und im Lehrbuch bereits gut aufgearbeitet.
Nachteil. Die Großteil der mentalen Arbeit liegt darin, die benötigte Zahlentheorie zu verstehen (keine Angst: es ist sehr elementare Zahlentheorie). Wenn man die verstanden hat, dann wirkt der Algorithmus beinahe trivial. Das Thema eignet sich schwer für graphische Darstellungen. Wenn Sie Computerfolien hassen und einen reinen Tafelvortrag halten wollen, dann ist dies Ihr Thema.
Mein Plan ist, dass wir uns in diesem Seminar gemeinsam einen "harten Brocken" der theoretischen Informatik vornehmen und uns durchbeißen. Dafür werden wir ihn in überschaubare Teile zerlegen und sie uns in mehreren Sitzungen und Vorträgen erarbeiten. Da ein Aspekt auf den vorherigen aufbaut, müssen wir uns gut absprechen und koordinieren.
Das Thema, das ich behandeln will, ist das allgemeine Derandomisierungsprojekt, das anstrebt, zu jedem effizienten randomisierten Algorithmus einen entsprechenden effizienten deterministischen Algorithmus zu konstruieren. Ein wichtiges Werkzeug dafür sind fehlerkorrigierende Codes, also ein Thema, das für sich genommen schon herausfordernd und interessant ist und welches den ersten Themenblock darstellen wird.
Error correcting codes. In diesem Themenblock will ich mit Ihnen die Begriffe der fehlerkorrigierenden Codes durchnehmen und erarbeiten, wie man solche konstruiert und was für Raten erreichbar sind.
Definitionen und erste Resultate. Sie führen grundlegende Begriffe ein und zeigen erste Konstruktionen (greedy, probabilistisch) und untere Schranken. Wir bekommen ein erstes Gefühl, was mit fehlerkorrigierenden Codes möglich ist.
Algebraische Konstruktionen und konkatenierte Codes. Hier sehen wir zum ersten Mal, wie man Codes mit positiver Rate konstruiert. Sie diskutieren auch, warum die probabilistischen Konstruktionen aus dem vorherigen Teilthema nicht wirklich praktikabel sind. Sie erläutern, was man unter einem konkatenierten Code versteht und wie man deren Minimalabstand und Rate verhalten.
Obere Schranken. Hier diskutieren Sie obere Schranken dafür, wie groß ein Code von bestimmten Minimalabstand werden kann. Stichwörter sind Johnson bound, Plotkin bound, Elias-Bassalygo bound. Literatur: Venkatesan Guruswamis Vorlesungsskript.
Zusätzliche Eigenschaften: lokal decodierbare Codes. Szenario: Sie haben eine Datenbank fehlerkorrigierend auf einem Medium abgespeichert. Wenn Ihre Datenbank $n$ Bits lang ist, dann haben Sie einen Code $C : \{0,1\}^n \rightarrow \{0,1\}^{n'}$ verwendet und die $n'$ Bits auf dem Datenträger gespeichert. Wenn Sie nun vielleicht 100 Bits lesen wollen, dann müssen Sie dennoch den ganzen String dekodieren. Die Idee lokal decodierbarer Codes ist, dass Sie, um 1 Bit des ursprünglichen Strings zu rekonstruieren, nur auf $k$ Bits der Codierung zugreifen müssen, wobei $k \ll n'$ gilt. Sie müssen also, wenn Sie einen kleinen Teil des ursprünglichen Strings rekonstruieren wollen, nur einen kleinen des codierten Strings lesen. Dies klingt sehr nach praktischer Anwendung, allerdings werden wir dieses Ergebnis im nächsten Themenblock, der sehr theoretisch ist, brauchen.
Derandomisierung aller schneller Algorithmen? Das ${\rm P} \stackrel{?}{=} {\rm BPP}$-Problem. Viele effiziente Algorithmen sind randomisiert, obwohl die Problemstellung deterministisch ist. Ein Paradebeispiel ist der Miller-Rabin-Algorithmus für Primzahlen. Dieser Themenblock behandelt ein Theorem, das besagt, dass unter vernünftigen komplexitätstheoretischen Annahmen jeder randomisierte Algorithmus derandomisiert werden kann.
Der Beweis besteht aus vielen Teilresultaten, jedes für sich selbst schon interessant. Wir haben Glück: das Thema ist im Lehrbuch Computational Complexity: A Modern Approach von Arora und Barak (draft pdf) bereits wunderbar aufbereitet.
Grundbegriffe. Hier wiederholen Sie Grundbegriffe wie P und BPP. Sie führen Begriffe ein wie pseudo random generator, distingusher und beweisen ein erstes überraschendes Ergebnis: ${\rm BPP} = {\rm P}/{\rm poly}$. Auf Deutsch: wenn ein Problem mit einem effizienten randomisierten Algorithmus gelöst werden kann, dann auch mit effizienten Schaltkreisen.
Distinguisher und Predictor Sie führen den Begriff des Predictors ein und zeigen, wie man aus einem Predictor einen Distinguisher baut. Sie rekapitulieren, wie sich das in das große Projekt der Derandomisierung einfügt.
Der Nisan-Wigderson-Generator. Hier taucht zum ersten Mal formal der Begriff der Schaltkreiskomplexität auf, insbesondere der average-case hardness einer Booleschen Funktion. Sie erklären die Konstruktion von Nisan und Wigderson und zeigen: wenn die verwendete Boolesche Funktion $f$ tatsächlich average-case-hard ist, dann ist der Output der Konstruktion pseudozufällig.
An diesem Punkt können wir zusammenfassen: wenn eine Boolesche Funktion $f$ in einfach exponentieller Zeit berechenbar ist und dennoch zumindest schwach exponentielle Average-Case-Hardness hat, dann gilt ${\rm P} = {\rm BPP}$. Dann können wir also zu jedem effizienten randomisierten Algorithmus einen effizienten deterministischen bauen.
Als nächstes geht es um Hardness-Amplification. Grob gesagt geht es darum, aus einer Booleschen Funktion, die hohe Worst-Case-Komplexität hat, eine zu bauen, die hohe Average-Case-Komplexität hat.
Worst-case- und Average-case-Komplexität, und Impagliazzos Hardcore-Lemma. Sie führen mehrere Begriffe der Schaltkreiskomplexität einer Booleschen Funktion ein (worst-case, average-case) und diskutieren zwei Parameter, die uns interessieren: die Schaltkreisgröße (mehr heißt schwieriger) und die Erfolgswahrscheinlichkeit (kleiner heißt schwieriger) und beweisen Impagliazzos Hardcore-Lemma: wenn eine Funktion $f$ schwierig ist, dann gibt es eine Teilmenge von Inputs, auf der $f$ extrem schwierig ist.
Milde und Starke Komplexität: Yaos XOR-Lemma. Sie schlagen die Brücke von Impagliazzos Hardcore-Lemma und unseren Begriffen von Average-Case-Komplexität und zeigen, wie man das Hardcore-Lemma verwenden kann, um aus einer ein wenig schwierigen Funktion eine extrem schwierige bauen kann.
Teilderandomisierung mittels lokal decodierbarer fehlerkorrigierender Codes. Sie rekapitulieren Begriffe fehlerkorrigierender Codes wie Rate, Abstand und lokale Decodierbarkeit. Sie erinnern uns daran, was wir im Teilthema 1.4 gelernt haben. Dann zeigen Sie, wie man lokal decodierbare fehlerkorrigierende Codes benutzt, um aus einer worst-case-schwierigen Booleschen Funktion einen Pseudozufallsgenerator bauen kann. Sie erläutern, warum dies noch nicht ausreicht, um davon ${\rm P} = {\rm BPP}$ abzuleiten.
Lokal listendecodierbare Codes. Dieses Thema geht nochmal zurück zu fehlerkorrigierenden Codes und zeigt, wie man deutlich bessere Code-Parameter erreichen kann (Rate, Abstand), wenn man zulässt, dass Codewörter nicht eindeutig rekonstruiert werden müssen, sondern akzeptiert, dass eine (kleine) Liste von möglichen Codewörtern zurückgeliefert werden. Sie zeigen, wie man diese listendecodierbaren Codes verwendet, um aus einer worst-case-schwierigen Funktion einen noch besseren Pseudozufallsgenerator bauen kann.
Eventuell müssen wir dieses Thema auf zwei Vorträge aufteilen: ein Vortrag zeigt, wie man diese listendecodierbaren Codes konstruiert, ein anderer zeigt, wie man diese im Kontext der Derandomisierung / der Pseudozufallsgeneratoren anwendet.
