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
First lecture: September 4th
Homework assignment 1
Homework assignment 2
Homework assignment 3
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
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
as well as masters students with appropriate backgrounds.
(Please feel free to discuss your backround with me to see
if it is suitable).
are also of course very welcome.
"Mathematical maturity", elementary probability theory and
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
There will be some homeworks and a final oral exam.
For masters students, the final might (or might not) be a written exam.
Jeff Steif (firstname.lastname@example.org)
Please email Jeff Steif (email@example.com) 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