Standard simplices and pluralities are not the most noise stable

DOI10.1007/S11856-016-1320-YzbMATH Open1361.60013arXiv1403.0885OpenAlexW2338393620MaRDI QIDQ314385FDOQ314385

Authors: Steven Heilman, Elchanan Mossel, Joe Neeman 

Publication date: 16 September 2016

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

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.

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

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

zbMATH Keywords

Gaussian noisepluralitydiscrete noisestandard simplex

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

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)