Standard simplices and pluralities are not the most noise stable

DOI10.1007/S11856-016-1320-YMaRDI QIDQ314385zbMATH OpenOpenAlexFDO

Authors Steven Heilman, Elchanan Mossel, Joe Neeman

Publication date 16 September 2016

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Gaussian noisepluralitydiscrete noisestandard simplex

Mathematics Subject Classification ID

Gaussian processes (60G15) Geometric probability and stochastic geometry (60D05)

Abstract: The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise stability respectively. These two conjectures are natural generalizations of the Gaussian noise stability result by Borell (1985) and the Majority is Stablest Theorem (2004). Here we show that the standard simplex is not the most stable partition in Gaussian space and that Plurality is not the most stable low influence partition in discrete space for every number of parts $kgeq3$, for every value $hoeq0$ of the noise and for every prescribed measures for the different parts as long as they are not all equal to $1/k$. Our results do not contradict the original statements of the Plurality is Stablest and Standard Simplex Conjectures in their original statements concerning partitions to sets of equal measure. However, they indicate that if these conjectures are true, their veracity and their proofs will crucially rely on assuming that the sets are of equal measures, in stark contrast to Borell's result, the Majority is Stablest Theorem and many other results in isoperimetric theory. Given our results it is natural to ask for (conjectured) partitions achieving the optimum noise stability.

Recommendations

• Euclidean partitions optimizing noise stability
• Three candidate plurality is stablest for small correlations
• Maximally stable Gaussian partitions with discrete applications
• Majority is stablest: discrete and SoS
• Majority is stablest: discrete and SoS
• Low correlation noise stability of symmetric sets
• Robust optimality of Gaussian noise stability
• A two-sided estimate for the Gaussian noise stability deficit
• Noise stability is computable and approximately low-dimensional

Cites work

• scientific article; zbMATH DE number 991499 (Why is no real title available?)
• scientific article; zbMATH DE number 1889799 (Why is no real title available?)
• scientific article; zbMATH DE number 3067044 (Why is no real title available?)
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• A course in minimal surfaces
• A two-sided estimate for the Gaussian noise stability deficit
• Approximate kernel clustering
• Double bubbles in Gauss space and spheres
• Euclidean partitions optimizing noise stability
• Generic mean curvature flow. I: Generic singularities
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• Geometric measure theory. A beginner's guide. Illustrated by James F. Bredt
• Maximally stable Gaussian partitions with discrete applications
• Minimal surfaces and mean curvature flow
• Noise stability of functions with low influences: invariance and optimality
• On the first and second variations of a nonlocal isoperimetric problem
• Open problems in soap bubble geometry
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Proof of the double bubble conjecture
• Riemannian geometry. A modern introduction
• Robust optimality of Gaussian noise stability
• Stability of hypersurfaces with constant mean curvature
• The Brunn-Minkowski inequality in Gauss space
• The Ehrhard inequality
• The round sphere minimizes entropy among closed self-shrinkers

Cited in

(6)

• Robust optimality of Gaussian noise stability
• Dimension Reduction for Polynomials over Gaussian Space and Applications
• Maximally stable Gaussian partitions with discrete applications
• Low correlation noise stability of symmetric sets
• Euclidean partitions optimizing noise stability
• Three candidate plurality is stablest for small correlations

This page was built for publication: Standard simplices and pluralities are not the most noise stable

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