15-859S / 21-801A: Analysis of Boolean Functions 2012

Meeting: Mondays and Wednesdays, 3pm-4:20pm, GHC 4101
First meeting: Monday, September 10
Instructor: Ryan O'Donnell (my 
email address)
Office Hours: GHC 7213, by appointment
Problem sets
Lecture videos
Course description
Boolean functions, f : {0,1}n → {0,1}, are perhaps the most basic object of study in theoretical computer science. They also arise in several other areas of mathematics, including combinatorics (graph theory, extremal combinatorics, additive combinatorics), metric and Banach spaces, statistical physics, and mathematical social choice. In this course we will study Boolean functions via their Fourier transform and other analytic methods. Highlights will include applications in property testing, social choice, learning theory, circuit complexity, pseudorandomness, constraint satisfaction problems, additive combinatorics, hypercontractivity, Gaussian geometry, random graph theory, and probabilistic invariance principles.

The main prerequisite is working knowledge of discrete probability. Also helpful will be undergraduate-level knowledge of linear algebra, asymptotic analysis, calculus, and computer science.

There will be about 6 problem sets, plus one writing project. The writing project will be given an interim grade and a final grade. The three components (homework, project interim grade, project final grade) will be weighted equally.