CS 252: Analysis of Boolean Functions

General Information

Instructor: Li-Yang Tan (Gates 466, liyang@cs.stanford.edu)
Classroom: Hewlett Teaching Center 103
Time: Mondays and Wednesdays, 4:30-5:50pm
Office hours: After class and by appointment

Course description

Boolean functions are among the most basic objects of study in theoretical computer science. This course is about the study of boolean functions from a complexity-theoretic perspective, with an emphasis on analytic methods. We will cover fundamental concepts and techniques in this area, including influence and noise sensitivity, polynomial approximation, hypercontractivity, probabilistic invariance principles, and Gaussian analysis. We will see connections to various areas of theoretical computer science, including circuit complexity, pseudorandomness, classical and quantum query complexity, learning theory, and property testing.

Prerequisites: CS103 and CS109. CS154 or CS161 recommended.


Analysis of Boolean Functions, by Ryan O'Donnell. Cambridge University Press, 2014.
See also References and supplementary reading material.

Tentative List of Topics

  • Influence, sensitivity, and noise stability
    Combinatorial interpretations; analytic formulas
    The noise operator
    Simple examples: k-CNFs and monotone functions
  • Halfspaces
    Halfspaces and their unique Chow parameters
    Peres's noise stability bound
    Polynomial threshold functions and the Gotsman-Linial conjecture
  • Decision trees and query complexity
    The O'Donnell-Saks-Schramm-Servedio inequality
    Randomized query complexity of monotone graph properties
    Quantum query complexity and the Aaronson-Ambainis conjecture
  • Boolean circuits
    Random restrictions and Håstad's switching lemma
    Fourier spectrum of DNFs and small-depth circuits
    Mansour's conjecture and the Fourier Entropy-Influence conjecture
  • Hardness amplification
    Impagliazzo's hard-core set theorem
    Yao's XOR lemma
    Amplification within NP and O'Donnell's theorem
    Dualities between hardness amplification and boosting
  • Learning under the uniform distribution
    Linial-Mansour-Nisan's low-degree algorithm
    Goldreich-Levin's query algorithm
    Agnostic learning via the Fourier transform
    Learning parities with noise and the junta problem
  • Property testing
    The Blum-Luby-Rubinfeld linearity test
    Blais's junta tests
  • Hypercontractivity
    Bonami's lemma
    The Kahn-Kalai-Linial theorem
    Friedgut's junta theorem
  • Limit theorems and Gaussian analysis
    The Berry-Esséen central limit theorem
    Lindeberg replacement method
    The Mossel-O'Donnell-Oleszkiewicz invariance principle
    Borell's isoperimetric inequality and Majority Is Stablest

  • If time permits:
    Pseudorandomness: bounded independence and small-bias spaces
    Uniform approximation by polynomials: symmetrization and Chebyshev polynomials
    Hardness of approximation: Håstad's hardness theorems, the Unique Games conjecture
    Social choice: Condorcet's paradox, Arrow's impossibility theorem, Friedgut-Kalai-Naor
    Additive combinatorics: the polynomial Freiman-Ruzsa conjecture
    Sharp threshold phenomena: Friedgut's, Bourgain's, and Hatami's sharp threshold theorems


Students taking the course for a letter grade:
•  Course project and in-class presentation
•  Scribing one lecture
Students taking the course for CR:
•  Brief overview of a research paper, or scribing one lecture
In-class discussions will be an important component of this course, and hence attendance will be expected.

References and supplementary reading material

Please follow this link.