Math 581A - Analysis of Boolean Functions - Fall 2025

Course information

  1. Introduction
  2. Linearity testing
  3. The Goldreich-Levin algorithm
  4. Hardness of Approximation I (via PCP Theorem + Parallel Repetition)
  5. Hypercontractivity
  6. The invariance principle
  7. The Majority is Stablest Theorem
  8. Hardness of Approximation II — The Unique Games Conjecture and Hardness for
    MaxCut
  9. Induced subgraphs of hypercubes
  10. The Aaronson-Ambainis Conjecture
  11. The Bohnenblust-Hille Inequality

Covered material

  1. Wednesday, Sep 24, 2025. FIRST DAY OF CLASS

Last day of class will be Friday, Dec 5, 2025.

Problem sets

 You can check your points on the GradeScope webpage.

Updates to the lecture notes