Three candidate plurality is stablest for small correlations

DOI10.1017/FMS.2021.56MaRDI QIDQ5154790zbMATH OpenOpenAlexFDO

Authors Steven Heilman, Alex Tarter

Publication date 5 October 2021

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

noise-stable partitions

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Minimal surfaces and optimization (49Q05) Minimal surfaces in differential geometry, surfaces with prescribed mean curvature (53A10)

Abstract: Using the calculus of variations, we prove the following structure theorem for noise stable partitions: a partition of $n$-dimensional Euclidean space into $m$ disjoint sets of fixed Gaussian volumes that maximize their noise stability must be $(m-1)$-dimensional, if $m-1leqn$. In particular, the maximum noise stability of a partition of $m$ sets in $mathbb{R}^n$ of fixed Gaussian volumes is constant for all $n$ satisfying $ngeqm-1$. From this result, we obtain: (i) A proof of the Plurality is Stablest Conjecture for $3$ candidate elections, for all correlation parameters $ho$ satisfying $0<ho<h{o}_0$, where $h{o}_0>0$ is a fixed constant (that does not depend on the dimension $n$), when each candidate has an equal chance of winning. (ii) A variational proof of Borell's Inequality (corresponding to the case $m=2$). The structure theorem answers a question of De-Mossel-Neeman and of Ghazi-Kamath-Raghavendra. Item (i) is the first proof of any case of the Plurality is Stablest Conjecture of Khot-Kindler-Mossel-O'Donnell (2005) for fixed $ho$, with the case $hoo{1}^{-}$ being solved recently. Item (i) is also the first evidence for the optimality of the Frieze-Jerrum semidefinite program for solving MAX-3-CUT, assuming the Unique Games Conjecture. Without the assumption that each candidate has an equal chance of winning in (i), the Plurality is Stablest Conjecture is known to be false.

Recommendations

• Maximally stable Gaussian partitions with discrete applications
• Standard simplices and pluralities are not the most noise stable
• Majority is stablest: discrete and SoS
• Euclidean partitions optimizing noise stability
• Majority is stablest: discrete and SoS

Cites work

• scientific article; zbMATH DE number 5971212 (Why is no real title available?)
• scientific article; zbMATH DE number 3329342 (Why is no real title available?)
• A selection principle for the sharp quantitative isoperimetric inequality
• A strong unique continuation theorem for parabolic equations
• A uniqueness theorem for parabolic equations
• Candidate hard unique game
• Designing stable elections
• Dimension Reduction for Polynomials over Gaussian Space and Applications
• Euclidean partitions optimizing noise stability
• Generic mean curvature flow. I: Generic singularities
• Improved approximation algorithms for MAX k-CUT and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Low correlation noise stability of symmetric sets
• Maximally stable Gaussian partitions with discrete applications
• Nodal sets for solutions of elliptic equations
• Nodal sets of solutions of parabolic equations: II
• Noise stability is computable and approximately low-dimensional
• Noise stability of functions with low influences: invariance and optimality
• Non interactive simulation of correlated distributions is decidable
• On non-optimally expanding sets in Grassmann graphs
• On the first and second variations of a nonlocal isoperimetric problem
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Proof of the double bubble conjecture
• Sharp dimension free quantitative estimates for the Gaussian isoperimetric inequality
• Social choice, computational complexity, Gaussian geometry, and Boolean functions
• Standard simplices and pluralities are not the most noise stable
• Symmetric convex sets with minimal Gaussian surface area
• The concentration of measure phenomenon
• The hyperplane is the only stable, smooth solution to the isoperimetric problem in Gaussian space
• The structure of Gaussian minimal bubbles

Cited in

(5)

• Sphere valued noise stability and quantum max-cut hardness
• Standard simplices and pluralities are not the most noise stable
• Euclidean partitions optimizing noise stability
• Maximally stable Gaussian partitions with discrete applications
• Probabilistic view of voting, paradoxes, and manipulation

This page was built for publication: Three candidate plurality is stablest for small correlations

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