Sommersemester 2016
Håstads Beweis
Inhalt
Ein berühmtes Ergebnis der Informatik ist, dass Schaltkreise konstanter Tiefe und polynomieller Größe die Parityfunktion nicht berechnen können. Furst, Saxe und Sipser lieferten den ersten Beweis, der von Andy Yao auf exponentielle untere Schranken verbessert wurde. Dieser Beweis ist allerdings sehr kompliziert. 1987 fand Johan Håstad einen wesentlich einfacheren Beweis, der hauptsächlich auf dem sogenannten Switching-Lemma beruht. Für diese Leistung erhielt er von der ACM die Auszeichnung für die beste Dissertation.
In diesem Seminar werden wir diesen Beweis im Detail betrachten. Das Ziel ist es, diesen komplett zu verstehen. Wir gehen dabei folgendermaßen vor: Jede Woche müssen alle Teilnehmerinnen und Teilnehmer für sich einen weiteren Teil des Textes lesen. Wir treffen uns wöchentlich für 90 Minuten, um diesen zu besprechen. Zunächst hält eine Teilnehmerin oder ein Teilnehmer einen kurzen (etwa zehnminütigen) Vortrag, anschließend diskutieren wir alle Details. Am Ende des Meetings gibt es eine kurze Zusammenfassung von einer oder einem zufällig ausgewählten Beteiligten.
Das Seminar gehört zum Bereich Theoretische Informatik. Es wird in deutscher Sprache durchgeführt.
Voraussetzungen zur Teilnahme
Liebe zur Mathematik und erfolgreiche Teilnahme an den Vorlesungen Stochastik, Analysis, Lineare Algebra und möglichst auch Berechenbarkeit und Komplexität.