15-859S 2007: Analysis of Boolean Functions

Meeting: Tuesdays and Thursdays, 12pm-1:20pm, NSH 3002
Instructor: Ryan O'Donnell (my 
email address)
Office Hours: WEH 7121, by appointment
Course Blog: http://boolean-analysis.blogspot.com

Homework (solutions available on request)

Lecture Notes (mostly unproofread; I don't vouch for the exact accuracy of any of them, including the ones I wrote)

Course Description
In this course we will explore the Fourier analysis of Boolean functions, f : {0,1}n → {0,1}. 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. The course is at a graduate level; advanced undergraduates may enroll with permission of the instructor.

The main prerequisite is mathematical maturity. Students must be comfortable with probability, and also with the basics of algorithmic analysis (big-O notation) and linear algebra.

There will be about 5 problem sets. Additionally, we will have graded scribe notes, which will have the same worth as problem sets. Students will probably be required to scribe 2 or 2.5 lectures.

Course Outline
A rough outline of the topics we will cover:

Related Material
There is no text for this course. Students may want to consult the online notes from related courses at other universities: Additional useful reading includes the survey on threshold phenomena and influence by Gil Kalai and Muli Safra, and Daniel Štefankovič's master's thesis.