Theory of Boolean Functions (7 1/2 points)
Fall 2018, 1st reading period

Lecturer and examinator: Jeffrey Steif

Class times and place
Tuesdays 10:15-12:00 and Fridays 15:15-17:00
Room: MVH11
First lecture: September 4th


Homework assignment 1
Homework assignment 2
Homework assignment 3

What have we done so far and what will we do next?

The aim of this course is to give an overview of the theory of Boolean functions. These arise
in probability theory, combinatorics and theoretical computer science. Some topics which will
be covered are the notions of influence, noise stability and sensitivity, randomized complexity
in theoretical computer science and Arrow's Theorem. Two key tools will be Fourier analysis
on the hypercube and hypercontractivity; no background concerning Fourier analysis and
hypercontractivity will be assumed.

This course is intended for graduate students in mathematics, mathematical statistics and
theoretical computer science as well as masters students with appropriate backgrounds.
(Please feel free to discuss your backround with me to see if it is suitable). Faculty
are also of course very welcome.

"Mathematical maturity", elementary probability theory and elementary analysis.

Course literature
We won't be following one particular book extremely closely but the two books most relevant to the course are the following.

Analysis of Boolean Functions by Ryan O'Donnell

Noise Sensitivity of Boolean Functions and Percolation by Christophe Garban and Jeffrey Steif

Examination Form:
There will be some homeworks and a final oral exam. For masters students, the final might (or might not) be a written exam.

Course Examinator:
Jeff Steif (

Registration: Please email Jeff Steif ( for registration. (If you are already on the email list, you do not need to do this.)

Last modified: Tuesday November 28 1 10:15:34 MET DST 2017