Math 581A - Analysis of Boolean Functions - Fall 2025

Course information

• Class schedule: MWF 10:30am - 11:20am in PDL C038
  
• Instructor:
  Thomas Rothvoss, rothvoss@uw.edu.
  Office hour: Wednesday 12:30-1:30 in PDL C440
  
• Course description: In this course we analyze functions on the vertices of the hypercube where the main
  tool of choice is Fourier analysis. We will see a rich set of applications to combinatorics and theoretical
  computer science, in particular hardness of approximation. The course is inspired by the terrific textbook
  by O’Donnell from 2014 where we add some more recent topics. Depending on the available time we plan to cover the following chapters:
  

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
    

• Prerequisites: This is a graduate class and a rigorous mathematical introduction to the analysis of boolean functions. Solid skills in linear algebra, analysis and probability will be helpful.
  
  
• Lecture notes: The main source and inspiration for this course is the textbook
  
  • Analysis of Boolean Functions by Ryan O'Donnell. Cambridge University Press 2014, ISBN 978-1-10-703832-5, pp. I-XX, 1-423.
    Available for free under https://arxiv.org/abs/2105.10386
  Additionally, lecture notes by the instructor of this course can be found here. Updates will be posted later. I would appreciate an email if you find a mistake/typo.
  
  
• Required Work:

• Your grade will be based on homework assignments. Homeworks are due weekly on Fridays on GradeScope. I will post homework problems on this webpage. Homework due in a particular week will be posted on Friday the week before (occasionally the posted homework will contain a problem based on material covered in the upcoming Monday lecture). 
• Students are expected to read the lecture notes in parallel to the lecture.
• NO EXAMS

• Collaboration policy: You may work with other students in finding solutions to homework problems. You may submit in groups up to 3 -- I expect everyone involved to have a sizable contribution.
  
• Discussion forum: Other than in office hours, you may ask questions on course content and homework on the course discussion forum.

Covered material

1. Wednesday, Sep 24, 2025. Sections 1.1 and 1.2 in the notes.
   
2. Friday, Sep 26, 2025. Convolution and restrictions.
   

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

Problem sets

• Problem set 1. Due Friday, Oct 3, 2025, 11pm on GradeScope.
  

Updates to the lecture notes

• Sep 23, 2025: Fixed statement of Prop 1.22 (2nd equation only holds for boolean case). In Lemma 1.32, rho-stable influence depends on f.
• Sep 26, 2025: Prop 1.10: The 2^n scaling  needed to be 2^(-n).
• Sep 29, 2025: Chapter 1: Finished restrictions. Started with noise stability