# 2012 Barbados Workshop on Computational Complexity

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.

Speaker:
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:
- 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.

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.

## Important Information for Participants