WiSe 16/17: Analyse Boolescher Funktionen
Nils Wisiol, Marian Margraf
Kommentar
Boolsche Funktionen sind eines der grundlegensten Objekte der theoretischen Informatik. Sie spilen wichtige Rollen in der Komplexitätstheorie, Kryptographie und dem Machine Learning sowie in weiteren Gebieten der Informatik und verwandten Disziplinen.
Der Inhalt dieser Vorlesung ist die Analyse von Boolschen Funktionen mit Hilfe der Fourierdarstellung und anderen Mitteln. In der harmonischen Analyse wird eine Boolsche Funktion als reelles, multilineares Polynom dargestellt. Viele kombinatorische Eigenschaften von Boolschen Funktionen, wie beispielsweise Linearität, Stabiliät, Einfluss und Lernbarkeit können mit dieser Darstellung betrachtet werden.
Die Vorlesung wird voraussichtlich auf Englisch gehalten und basiert auf dem Lehrbuch von Ryan O'Donnell (analysisofbooleanfunctions.org); einige mathematische Vorkenntnisse werden vorausgesetzt. Die Teilnehmer müssen wöchtenliche Hausaufgaben lösen und sie in den Übungen vorstellen. In einer Projekthausaufgabe wird ein Machine Learning Algorithmus aus der Vorlesung implementiert.
Schließen16 Termine
Regelmäßige Termine der Lehrveranstaltung