## 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