Hypercontractivity made easy, and sharp threshold theorems: Lecture 1

Tuesday, July 30, 2013 - 3:00pm to 6:00pm
Location: 
MSR New England (Barton room on the 1st floor of One Memorial Drive building)m
Speaker: 
Ryan O'Donnell
Biography: 
Carnegie Mellon University

In this lecture I'll introduce the "Hypercontractivity Theorem" for
real-valued functions on the boolean cube, f : {-1,1}^n -> R and
explain how you can view it as either:
. a natural strengthening of Holder's inequality;
. an isoperimetric statement saying that among small-volume sets
in {-1,1}^n, Hamming balls have the smallest boundary (roughly
speaking).
We'll see a new(?), essentially trivial reduction to the case of
n=1, where it's easy. This means that the isoperimetric statement for
{-1,1}^n follows from an analogous isoperimetric statement for {-1,1}.
(!) I'll also show some applications of the Hypercontractivity
Theorem, including the "KKL Theorem".
Toward the end of the lecture I will show how to generalize all of
these results to functions on any product probability space, in part
by using the technique of "randomization/symmetrization".