Courses

Boolean function analysis is the study of functions on the Boolean cube $\{\pm1\}^n$ and related domains from a spectral perspective. It has become an essential tool in many areas of theoretical computer science, combinatorics, and probability theory.

I am preparing lecture notes. Also relevant are the lecture notes from the previous offering of this course.

Office hours: By e-mail appointment. You can also drop by my room (519), or call first (4876).

Please e-mail me so I can add you to the course mailing list.

Topics covered include:

• Classical material:
  • Basic definitions: Fourier expansion, influence, noise.
  • Basic results: Friedgut–Kalai–Naor theorem, Kahn–Kalai–Linial theorem, Friedgut’s junta theorem.
  • Hypercontractivity.
  • $p$-biased analysis and the Russo–Margulis formula.
• Applications:
  • Linearity testing.
  • Approximate polymorphisms.
  • Hardness of approximating MAX-3LIN.
• $p$-biased analysis for small $p$: global hypercontractivity, Bourgain’s sharp threshold theorem.

More topics will be added later.

Topics covered in class:

1. January 18: Introduction and linearity testing (Section 1).
2. January 25: Exact polymorphisms of Majority (Section 2).
3. February 1: Approximate polymorphisms of Majority (Section 3) and Arrow’s theorem (Section 4).
4. February 8: Friedgut–Kalai–Naor theorem (Section 5).
5. February 15: Hardness of linear equations (Section 6).
6. February 22: Hypercontractivity (Section 7).
7. February 29: Influence (Section 8).
8. March 7: Biased Fourier analysis (Section 9) and intro to next week (Section 10.1).
9. March 14: Global hypercontractivity (Section 10), skipping Section 10.4.
10. March 21: Decision trees (Section 11).
11. March 26 (Taub 5, 10:30): Complexity measures (Section 12) up to (and including) Section 12.5.
12. April 2 (Taub 6, 10:00): Remainder of Section 12.

Assignments:

1. Assignment 1, posted February 8, 2024, due February 29, 2024. Solution.
2. Assignment 2, posted March 4, 2024 (partially relying on material taught on March 7), due March 28, 2024. Solution.
3. Assignment 3, posted March 4, 2024 (partially relying on material taught on March 28 or April 4), due May 18, 2024. Solution.