CS 252: Analysis of Boolean Functions

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

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.

• 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
  ...

•  Course project and in-class presentation
•  Scribing one lecture

•  Brief overview of a research paper, or scribing one lecture

Please follow this link.