Robust optimality of Gaussian noise stability

DOI10.4171/JEMS/507MaRDI QIDQ2019201zbMATH OpenFDO

Authors Elchanan Mossel, Joe Neeman

Publication date 27 March 2015

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4126

zbMATH Keywords

Gaussian noise sensitivityinfluenceisoperimetrymax-cut

Mathematics Subject Classification ID

Inequalities involving derivatives and differential and integral operators (26D10) Inequalities; stochastic orderings (60E15) Stationary stochastic processes (60G10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We prove that under the Gaussian measure, half-spaces are uniquely the most noise stable sets. We also prove a quantitative version of uniqueness, showing that a set which is almost optimally noise stable must be close to a half-space. This extends a theorem of Borell, who proved the same result but without uniqueness, and it also answers a question of Ledoux, who asked whether it was possible to prove Borell's theorem using a direct semigroup argument. Our quantitative uniqueness result has various applications in diverse fields.

Review text

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.

Recommendations

• A two-sided estimate for the Gaussian noise stability deficit
• Low correlation noise stability of symmetric sets
• A multidimensional version of noise stability
• Noise stability and correlation with half spaces
• Standard simplices and pluralities are not the most noise stable

Cites work

• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• A functional form of the isoperimetric inequality for the Gaussian measure
• Comparison theorems for exit times
• Conditional hardness for approximate coloring
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lévy-Gromov's isoperimetric inequality for an infinite dimensional diffusion generator
• Majority is stablest: discrete and SoS
• Maximally stable Gaussian partitions with discrete applications
• Noise sensitivity of Boolean functions and applications to percolation
• On the cases of equality in Bobkov's inequality and Gaussian rearrangement
• On the isoperimetric deficit in Gauss space
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn.
• Social Indeterminacy
• Spherical rearrangements, subharmonic functions, and \(\ast\)-functions in \(n\)-space
• The Brunn-Minkowski inequality in Gauss space
• The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
• Towards sharp inapproximability for any 2-CSP
• Éléments extrémaux pour les inégalités de Brunn-Minkowski gaussiennes (Extreme elements for the Gaussian Brunn-Minkowski inequalities)

Cited in

(22)

• Maximally stable Gaussian partitions with discrete applications
• A fractional isoperimetric problem in the Wiener space
• The structure of Gaussian minimal bubbles
• Symmetry of minimizers of a Gaussian isoperimetric problem
• Stability of the logarithmic Sobolev inequality via the Föllmer process
• Robust dimension free isoperimetry in Gaussian space
• Robustness of the Gaussian concentration inequality and the Brunn-Minkowski inequality
• A multidimensional version of noise stability
• Low correlation noise stability of symmetric sets
• Standard simplices and pluralities are not the most noise stable
• Noise Assisted High-gain Stabilization: Almost Surely or in Second Mean
• Isoperimetric functional inequalities via the maximum principle: the exterior differential systems approach
• A two-sided estimate for the Gaussian noise stability deficit
• Probabilistic view of voting, paradoxes, and manipulation
• scientific article; zbMATH DE number 7140483 (Why is no real title available?)
• Remarks on Gaussian noise stability, Brascamp-Lieb and Slepian inequalities
• Common Information, Noise Stability, and Their Extensions
• On multiple peaks and moderate deviations for the supremum of a Gaussian field
• Hypercontractivity for global functions and sharp thresholds
• Analysis of high-dimensional distributions using pathwise methods
• Euclidean partitions optimizing noise stability
• Noise stability of functions with low influences: invariance and optimality

This page was built for publication: Robust optimality of Gaussian noise stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019201)