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
Homeworks:
Homework assignment 1
Homework assignment 2
Homework assignment 3
COURSE GOALS:
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.
INTENDED AUDIENCE:
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.
Prerequisites:
"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 (steif@chalmers.se)
Registration:
Please email Jeff Steif (steif@chalmers.se) 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