The 24th McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 26th to March 4th, 2012. Participants are expected to arrive on Sunday afternoon, February 26th. The subject of this year's workshop will be Analysis of Boolean Functions.
Ryan O'Donnell
Carnegie Mellon University
Analysis of Boolean Functions
Boolean functions, f : {0,1}^n -> {0,1}, are perhaps the most basic object of study in computer science. In this workshop we will investigate them via their Fourier transform and other analytic methods. Besides developing basic techniques, we will see the emergence of a number of themes:Finally, we will see the tools and themes of Analysis of Boolean Functions applied to problems in learning theory, communication complexity, property testing, NP-hardness of approximation, and random graph theory.
- The dichotomy between juntas and functions with small influences.
- Noise stability as a bridge between combinatorial and Fourier-analytic properties of a function.
- The Boolean cube is a small-set expander.
- Functions on Gaussian space are a special case of Boolean functions.
- Low-degree functions of well-behaved random variables are well-behaved.
- Invariance: for low-influence functions, only the first two moments of the inputs matter.