WiSe 17/18: Analysis of Boolean Functions
Nils Wisiol, Marian Margraf
Comments
Boolean functions are one of the most fundamental objects to study in theoretical computer science. They play important roles in computational complexity, cryptography, machine learning, and many more areas of computer science and neighbouring fields.
The subject of this class is the analysis of Boolean functions via their Fourier expansion and other analytic means. In this “harmonic” analysis, a Boolean function is represented as a real multilinear polynomial. Many combinatorial properties of Boolean functions, such as linearity, stability, influences, and learnability can be studied using this representation.
The class will be taught in English and based on the textbook by Ryan O'Donnell (analysisofbooleanfunctions.net); some mathematical background is required. Students are required to solve weekly homework problems and present them in the recitation sessions. A project-style homework will include programming a machine learning algorithm based on the analytic results presented in class.
close16 Class schedule
Regular appointments