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: TBD 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 (TBD).
Covered material
- 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