UC Berkeley

We study two kinds of extremal subsets of Gaussian space:

sets which minimize the surface area, and sets which minimize the noise sensitivity.

For both problems, affine half-spaces are extremal: in the case of surface area,

this is was discovered independently by Borell and by Sudakov and Tsirelson in the 1970s;

for noise sensitivity, it is due to Borell in the 1980s.

We give a self-contained treatment of these two subjects,

using semigroup methods. For Gaussian surface area, these methods were developed by

Bakry and Ledoux, but their application to noise sensitivity is new.

Compared to other approaches to these two problems, the semigroup method has the

advantage of giving accurate characterizations of the extremal and near-extremal sets.

We review the Carlen-Kerce argument showing that (up to null sets) half-spaces are the

unique minimizers of Gaussian surface area. We then give an analogous argument

for noise sensitivity,

proving that half-spaces are also the unique minimizers of noise sensitivity.

Unlike the case of Gaussian isoperimetry, not even a partial characterization of

the minimizers of noise sensitivity was previously known.

After characterizing the extremal sets, we study near-extremal sets. For both surface

area and noise sensitivity, we show that near-extremal sets must be close to half-spaces.

Our bounds are dimension-independent, but they are not sharp.

Finally, we discuss some applications of noise sensitivity: in economics, we

characterize the extremal voting methods in

Kalai's quantitative version of Arrow's impossibility theorem. In computer science,

we characterize the optimal rounding methods in Goemans and Williamson's semidefinite

relaxation of the Max-Cut problem.