Robust optimality of Gaussian noise stability (Q2019201)

The famous Borell theorem says that half-spaces have optimal stability among all sets with a given Gaussian measure. In this paper, the authors give a novel proof for this result and its discrete applications and answer the question whether semigroup methods can be used to give a short and direct proof for the Borell inequality. They first demonstrate that half-spaces are the unique optimizers of Gaussian stability and then show that if the stability of a set is close to optimal given its measure, then the set must be close to a half-space. The authors derive from their Gaussian results some of the main discrete applications of Borell theorem, including a robust version of the ``majority is stablest'' theorem which in turn implies a robust version of the quantitative Arrow theorem in economics. The robust noise stability has specifically an application in the analysis of the well-known max-cut optimization problem. In this problem, one seeks a partition of a graph into two pieces such that the number of edges from one piece to the other is maximal.