Gaussian bubble clusters

Suppose I ask you to divide \(\mathbb{R}^n\) into two pieces of fixed Gaussian measure so that the surface area of the boundary is as small as possible. The Gaussian isoperimetric inequality states that the best way to do it is by cutting \(\mathbb{R}^n\) with a hyperplane:

Gaussian half-space

Now what if I ask for three parts instead of two? ...more

June 15, 2020

Gaussian noise sensitivity

Suppose that \(X\) and \(Y\) are positively correlated standard Gaussian vectors in \(\mathbb{R}^n\). Define the noise sensitivity of \(A \subset \mathbb{R}^n\) to be the probability that \(X \in A\) and \(Y \not \in A\). Borell proved that for any \(a \in (0,1)\), half-spaces minimize the noise sensitivity subject to the constraint \(\mathrm{Pr}(X \in A)=a\). This inequality can be seen as a strengthening of the Gaussian isoperimetric inequality: in the limit as the correlation goes to one the noise sensitivity is closely related to the surface area, because if \(X \in A\) and \(Y \not \in A\) are close together then they're probably both close to the boundary of \(A\). From a more applied point of view, Borell's inequality and its discrete relatives played a surprising and crucial role in studying hardness of approximation in theoretical computer science. ...more

June 15, 2020