Explore the mathematical foundations and applications of Boolean function analysis through this comprehensive graduate-level lecture series delivered by Ryan O'Donnell at Carnegie Mellon University in Fall 2012. Master fundamental concepts beginning with Fourier expansions and basic formulas, then progress through probability densities, BLR linearity testing, and social choice theory. Delve into advanced topics including noise stability, Arrow's Theorem, spectral concentration, and learning theory. Examine restrictions and the Goldreich-Levin Theorem, DNF formulas, and the Linial-Mansour-Nisan Theorems. Study majority functions, linear threshold functions (LTFs), and the Central Limit Theorem, followed by noise stability analysis and the level-1 inequality. Investigate Bonami's Lemma, the KKL Theorem, dictator testing, and the FKN Theorem. Explore connections to probabilistically checkable proofs, constraint satisfaction problems, and Håstad's hardness theorems. Understand UG-hardness results from dictator tests and the Hypercontractivity Theorem. Analyze invariance theorems and the Majority Is Stablest Theorem. Conclude with additive combinatorics, Sanders's Theorem, and current open problems in the field. Requires undergraduate-level computer science theory knowledge and mathematical maturity for full comprehension of the advanced theoretical concepts presented across 23 detailed lectures.

Syllabus

Analysis of Boolean Functions at CMU - Lecture 1: The Fourier expansion and basic formulas
Analysis of Boolean Functions at CMU - Lecture 2: Probability densities and BLR linearity testing
Analysis of Boolean Functions at CMU - Lecture 3: Social choice and influences
Analysis of Boolean Functions at CMU - Lecture 4: Noise stability and Arrow's Theorem
Analysis of Boolean Functions at CMU - Lecture 5: Spectral concentration and learning
Analysis of Boolean Functions at CMU - Lecture 6: Restrictions and the Goldreich--Levin Theorem
Analysis of Boolean Functions at CMU - Lecture 7: DNF formulas
Analysis of Boolean Functions at CMU - Lecture 8: Linial--Mansour--Nisan Theorems
Analysis of Boolean Functions at CMU - Lecture 9: Majority, LTFs, and the CLT
Analysis of Boolean Functions at CMU - Lecture 10: LTFs and noise stability
Analysis of Boolean Functions at CMU - Lecture 11: Level-1 inequality and the 2/pi Theorem
Analysis of Boolean Functions at CMU - Lecture 12: Bonami's Lemma and the KKL Theorem
Analysis of Boolean Functions at CMU - Lecture 13: Dictator Testing and the FKN Theorem
Analysis of Boolean Functions at CMU - Lecture 14: Probabilistically checkable proofs of proximity
Analysis of Boolean Functions at CMU - Lecture 15: Constraint satisfacation problems
Analysis of Boolean Functions at CMU - Lecture 16: Håstad's hardness theorems
Analysis of Boolean Functions at CMU - Lecture 17: UG-hardness results from dictator tests
Analysis of Boolean Functions at CMU - Lecture 18: The Hypercontractivity Theorem
Analysis of Boolean Functions at CMU - Lecture 19: Invariance theorems
Analysis of Boolean Functions at CMU - Lecture 20: Majority Is Stablest Theorem
Analysis of Boolean Functions at CMU - Lecture 21: Additive combinatorics
Analysis of Boolean Functions at CMU - Lecture 22: Sanders's Theorem
Analysis of Boolean Functions at CMU - Lecture 23: Open problems