http://www.cs.cmu.edu/~odonnell/boolean-analysis

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.  (See below for a partial list.)  The course will be at a graduate level; advanced undergraduates may enroll with permission of the instructor.


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

TEXT:
There will be no text.  Students may consult online notes from related
courses; see the list on the course web page.

METHOD OF EVALUATION:
Grading will be based on a few problem sets.  There may also be a final
project involving writing a report on a paper.


TOPICS TO BE COVERED:

* Basics of harmonic analysis of Boolean functions -- influences, average sensitivity and noise sensitivity, juntas, hypercontractivity.
* Probabilistically checkable proofs and sharp hardness-of-approximation results.
* Learning theory, under the uniform distribution.
* Voting and social choice.
* Property testing.

TOPICS THAT MAY BE COVERED, BASED ON TIME & INTEREST:

* Complexity and lower bounds.
* Percolation and statistical physics.
* Metric embeddings.
* Arithmetic progressions.
* Communication complexity.
* Coding theory.