Robust optimality of Gaussian noise stability

DOI10.4171/JEMS/507zbMATH Open1384.60062arXiv1210.4126MaRDI QIDQ2019201FDOQ2019201

Authors: Elchanan Mossel, Joe Neeman 

Publication date: 27 March 2015

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

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.

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

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

zbMATH Keywords

influenceisoperimetrymax-cutGaussian noise sensitivity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

• Isoperimetric Functional Inequalities via the Maximum Principle: The Exterior Differential Systems Approach
• Hypercontractivity for global functions and sharp thresholds
• Stability of the logarithmic Sobolev inequality via the Föllmer process
• Noise stability of functions with low influences: invariance and optimality
• Standard simplices and pluralities are not the most noise stable
• Remarks on Gaussian Noise Stability, Brascamp-Lieb and Slepian Inequalities
• A two-sided estimate for the Gaussian noise stability deficit
• Robust dimension free isoperimetry in Gaussian space
• The structure of Gaussian minimal bubbles
• Noise Assisted High-gain Stabilization: Almost Surely or in Second Mean
• On multiple peaks and moderate deviations for the supremum of a Gaussian field
• Robustness of the Gaussian concentration inequality and the Brunn-Minkowski inequality
• Common Information, Noise Stability, and Their Extensions
• Maximally stable Gaussian partitions with discrete applications
• Symmetry of minimizers of a Gaussian isoperimetric problem
• A fractional isoperimetric problem in the Wiener space
• Probabilistic view of voting, paradoxes, and manipulation
• Analysis of high-dimensional distributions using pathwise methods
• Low correlation noise stability of symmetric sets
• Title not available (Why is that?)

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)