Thomas Rothvoss

Math 581A - Analysis of Boolean Functions - Fall 2025

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:

Introduction
Linearity testing
The Goldreich-Levin algorithm
Hardness of Approximation I (via PCP Theorem + Parallel Repetition)
Hypercontractivity
The invariance principle
The Majority is Stablest Theorem
Hardness of Approximation II — The Unique Games Conjecture and Hardness for
MaxCut
Induced subgraphs of hypercubes
The Aaronson-Ambainis Conjecture
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.

Wednesday, Sep 24, 2025. Sections 1.1 and 1.2 in the notes.
Friday, Sep 26, 2025. Convolution and restrictions.
Monday, Sep 29, 2025: Chapter 1: Finished restrictions. Started with noise stability
Wednesday, Oct 1, 2025: Noise stability
Friday, Oct 3, 2025: Finished Chapter 1
Monday, Oct 6, 2025: Chapter 2: Linearity test
Wednesday, Oct 8, 2025: Chapter 3: The Goldreich-Levin algorithm
Friday, Oct 10, 2025: List decoding of Walsh-Hadamard code. Chapter 4: PCP verifiers and constraint satisfaction.
Monday, Oct 13, 2025: Chapter 4: Label Cover
Wednesday, Oct 15, 2025: Chapter 4: Parallel repetition, beginning of Noisy Linearity Test
Friday, Oct 15, 2025. Chapter 4: The Noisy Linearity + constraint test.

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

You can check your points on the GradeScope webpage.

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.