Analysis of Boolean Functions (2013, Berkeley)

This fall I am giving a course at Berkeley on analysis of Boolean functions

Course number: CS 294-92
Title: Analysis of Boolean Functions
Lectures: TuTh 5:00-6:30
Location: Room 310 Soda

First lecture will be was on Thursday August 29th at 5:00pm.

Graduate students in computer science and in mathematics are welcomed. Advanced undergraduates may find it useful as well.

My plan is to emphasize applications to extremal combinatorics, random graphs, percolation and related stochastic models, and social choice and to mention applications to and connections with the theory of computing. So I will try to give self contained presentations for some central themes and questions in these areas.

Important announcement: Real analysis boot camp in the Simons Institute for the Theory of Computing, is part of the program in Real Analysis and Computer Science. It is taking place on September 9-13 and has three lecture series. All lecture series are related to the topic of the course and especially:

Introduction to Analysis on the Discrete Cube  Krzysztof Oleszkiewicz, University of Warsaw

Outline of the course: Boolean functions are central objects in combinatorics, complexity theory, probability theory and other areas of mathematics and computer science.  This course discusses  analysis of Boolean functions and various applications to these areas.  The course will run over 14 weeks, with two 80-minute lectures per week.  

Week I: Collective coin flipping (randomness in distributed computing). The discrete cube, Boolean functions, influence of variables and edge expansion.  Basic examples and the example of tribes. 

Week II: Extremal Combinatorics central results and open problems. (Erdos-Ko-Rado/Kruskal-Katona/, Sauer-Shelah, Harris-Kleitman, Capset, Frankl, Erdos-Rado, Chvatal)

Week III: Discrete isoperimetric results, general review, lower bounds for edge expansion: combinatorial proofs.

Week IV-V: Fourier analysis on the discrete cube and the relation with influences and edge expansion. Khintchine inequalities and Bonamie-Beckner inequalities.  Edge expansion inequalities revisited. Proof of the KKL theorem; some consequences, extensions and sharper forms. Consequences for random walks on the discrete cube.

Week VI: Social choice theory:  – What is social choice theory about. An application: Arrow’s theorem in social choice and other related applications. 

Week VII, VIII: Random graph theory – some central results and problems. Threshold behavior: review of Russo’s lemma and application of the KKL theorem to sharp thresholds for graph properties.  Applications of the Margulis-Talagrand inequality: the case of a large group of symmetries and the case of small critical probabilities.

Weeks IX: Applications to extremal combinatorics.

Week X-XI: Percolation and related models of statistical physics. A few central results and problems. Applications to the study of crossing event in percolation, tail estimates, and first passage percolation.

Weeks XII-XIV: Noise sensitivity and noise stability  Correlation inequalities

, a few connections with computational complexity, learnability and other questions in TOC,  some central open problems

Resources (to be updates): There are two books in progress:  Noise Sensitivity and Percolation. Lecture Notes by Christophe Garban and Jeff Steif; Ryan O’Donnell: Analysis of Boolean Function.