- Textbook in progress

- Spring 2007 version of this course, with lecture notes

- Course bulletin/discussion board. To access it:
- Go to https://piazza.com/cmu
- In one of the class slots, search for "15-859S / 21-801A: Analysis of Boolean Functions".
- Put in the access code
**aobf12**and click "Join as Student". - Click "Add Class".
- It will then request your "cmu.edu email address". However
**you can actually use any email address**. - Follow the subsequent instructions.

- Homework 1 (homework1.tex, aobf.sty, hemi-icosahedron.pdf) -- due Monday Sept. 17

- Homework 2 (homework2.tex) -- due Monday Sept. 24

- Homework 3 (homework3.tex) -- due Monday Oct. 1

- Homework 4 (homework4.tex) -- due Monday Oct. 8

- Homework 5 (homework5.tex) -- due Monday Oct. 15

- Homework 6 (homework6.tex) -- due Wednesday Oct. 24

- Lecture 1 -- The Fourier expansion and basic formulas (picture-in-picture .mp4)

- Lecture 2 -- Probability densities, convolution, BLR linearity testing (.mp4)

- Lecture 3 -- Social choice and influences (.mp4)

- Lecture 4 -- Noise stability and Arrow's Theorem (.mp4)

- Lecture 5 -- Spectral concentration and learning (.mp4)

- Lecture 6 -- Restrictions and the Goldreich-Levin Theorem (.mp4)

- Lecture 7 -- DNF formulas (.mp4)

- Lecture 8 -- Linial-Mansour-Nisan Theorems (.mp4)

- Lecture 9 -- Majority, LTFs, and the CLT (.mp4)

- Lecture 10 -- LTFs and noise stability (.mp4)

- Lecture 11 -- Level-1 Inequality, 2/π Theorem, reasonable random variables (.mp4)

- Lecture 12 -- Bonami Lemma and KKL Theorem (.mp4)

(contains an incorrect justification of the simple Markov inequality argument used in the KKL proof; oops)

- Lecture 13 -- Dictator Testing and the FKN Theorem (.mp4)

- Lecture 14 -- Probabilistically checkable proofs of proximity (.mp4)

- Lecture 15 -- Constraint satisfaction problems (.mp4)

- Lecture 16 -- Håstad's hardness theorems (.mp4)

- Lecture 17 -- UG-hardness from dictator tests (.mp4), lecture by John Wright

- Lecture 18 -- The Hypercontractivity Theorem (.mp4)

- Lecture 19 -- Invariance theorems (.mp4)

- Lecture 20 -- Majority Is Stablest theorem (.mp4)

- Lecture 21 -- Additive combinatorics (.mp4)

- Lecture 22 -- Sanders's Theorem (.mp4)

- Lecture 23 -- Open problems (.mp4)

Boolean functions, f : {0,1}

**Prerequisites**

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.

**Evaluation**

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.