WiSe 17/18: Analyse Boolescher Funktionen
Nils Wisiol, Marian Margraf
Kommentar
Boolesche Funktionen sind eines der grundlegendsten Objekte der theoretischen Informatik. Sie spielen 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 Booleschen Funktionen mit Hilfe der Fourierdarstellung und anderen Mitteln. In dieser “harmonischen” Analyse wird eine Boolesche Funktion als reelles, multilineares Polynom dargestellt. Viele kombinatorische Eigenschaften von Booleschen Funktionen, wie beispielsweise Linearität, Stabilitä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.net); 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