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.
3. Monday, Sep 29, 2025: Chapter 1: Finished restrictions. Started with noise stability
4. Wednesday, Oct 1, 2025: Noise stability
5. Friday, Oct 3, 2025: Finished Chapter 1
6. Monday, Oct 6, 2025: Chapter 2: Linearity test
   
7. Wednesday, Oct 8, 2025: Chapter 3: The Goldreich-Levin algorithm
8. Friday, Oct 10, 2025: List decoding of Walsh-Hadamard code. Chapter 4: PCP verifiers and constraint satisfaction.
   
9. Monday, Oct 13, 2025: Chapter 4: Label Cover
10. Wednesday, Oct 15, 2025: Chapter 4: Parallel repetition, beginning of Noisy Linearity Test
11. Friday, Oct 15, 2025. Chapter 4: The Noisy Linearity + constraint test.
    
12. Monday, Oct 20, 2025. Chapter 4: The reduction from Label Cover to 3LIN.
    
13. Wednesday, Oct 22, 2025. Chapter 4: Finished the reduction and started with Chapter 5: B-reasonable random variables
14. Friday, Oct 24, 2025: Chapter 5: Proof of Bonami Lemma.
15. Monday, Oct 27, 2025: Chapter 5: FKN Theorem. Majority function. Tribes function.
16. Wednesday, Oct 29, 2025: Chapter 5: The KKL Theorem.
17. Friday, Oct 31, 2025: Started with general hypercontractivity.
18. Monday, Nov 3, 2025: Two Point Inequality for n=1.
19. Wednesday, Nov 5, 2025: General Hypercontractivity
    
20. Friday, Nov 7, 2025: Friedgut's Junta Theorem
    

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

Problem sets

• Problem set 1. Due Friday, Oct 3, 2025, 11pm on GradeScope.
• Problem set 2. Due Friday, Oct 10, 2025, 11pm on GradeScope.
• Problem set 3. Due Friday, Oct 17, 2025, 11pm on GradeScope.
• Problem set 4. Due Friday, Oct 24, 2025, 11pm on GradeScope.
• Problem set 5. Due Friday, Oct 31, 2025, 11pm on GradeScope.
• Problem set 6. Due Friday, Nov 7, 2025, 11pm on GradeScope.
• Problem set 7. Due Friday, Nov 14, 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).
• Oct 1, 2025: Moved the I[f] <= deg(f) bound from Chapter 10 to Chapter 1. Chapter 2: Def of dist needed != instead of =.
• Oct 8, 2025: Expanded the chapter on the Goldreich-Levin algorithm a bit.
• Oct 13, 2025: Corrected the soundness vs completeness parameter in Chapter 4.
• Oct 22, 2025: Added a comment on Max-3SAT hardness at end of Chapter 4. g^2(S) needed to be g^2(S)^2 in the FKN Theorem.
• Oct 24, 2025: Chapter 4: Fixed a few typos. Added a remark concerning Bonami's Lemma.
• Oct 25, 2025: Rewrite parts of Chapter 10 (in particular the FBS bound).
• Oct 29, 2025: Streamlined the calculation in the proof of the KKL Theorem.
• Oct 31, 2025: Rewrote Chapter 10.12.
• Nov 3, 2025: Expanded the proof of the Two Point Inequality for n=1.
• Nov 7, 2025: Rewrote the noisy hypercube application.