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