CSAIL Event Calendar

Analysis of Boolean Functions

Boolean functions, f : {0,1}n → {0,1}, are a basic object of study in theoretical computer science. In this seminar we will study Boolean functions via their Fourier transform and other analytic methods. The powerful techniques from this field have application in numerous areas of computer science. We will spend some time developing the area's basic mathematics; however, the main focus will be on applications, in CS theory and beyond.
Highlights will include applications in constraint satisfaction problems, learning theory, circuit complexity, pseudorandomness, additive combinatorics, hypercontractivity, property testing, social choice, Gaussian geometry, random graph theory, and probabilistic invariance principles.

See other events happening in February 2013