Fall 2013

Robust Gaussian Noise Stability

Tuesday, Aug. 27, 2013 9:00 am9:45 am

Add to Calendar

Given two Gaussian vectors that are positively correlated, what is the probability that they both land in some fixed set A? Borell proved that this probability is maximized (over sets A with a given volume) when A is a half-space. We will give a new and simple proof of this fact, which also gives some stronger results. In particular, we can show that half-spaces uniquely maximize the probability above, and that sets which almost maximize this probability must be close to half-spaces. We will also mention some applications to testing, and to the analysis of the Goemans-Williamson algorithm.