Hyperstable Sets with Voting and Algorithmic Hardness Applications
From MaRDI portal
Abstract: The noise stability of a Euclidean set with correlation is the probability that , where are standard Gaussian random vectors with correlation . It is well-known that a Euclidean set of fixed Gaussian volume that maximizes noise stability must be a half space. For a partition of Euclidean space into parts each of Gaussian measure , it is still unknown what sets maximize the sum of their noise stabilities. In this work, we classify partitions maximizing noise stability that are also critical points for the derivative of noise stability with respect to . We call a partition satisfying these conditions hyperstable. Uner the assumption that a maximizing partition is hyperstable, we prove: * a (conditional) version of the Plurality is Stablest Conjecture for or candidates. * a (conditional) sharp Unique Games Hardness result for MAX-m-CUT for or * a (conditional) version of the Propeller Conjecture of Khot and Naor for sets. We also show that a symmetric set that is hyperstable must be star-shaped. For partitions of Euclidean space into parts of fixed (but perhaps unequal) Gaussian measure, the hyperstable property can only be satisfied when all of the parts have Gaussian measure . So, as our main contribution, we have identified a possible strategy for proving the full Plurality is Stablest Conjecture and the full sharp hardness for MAX-m-CUT: to prove both statements, it suffices to show that sets maximizing noise stability are hyperstable. This last point is crucial since any proof of the Plurality is Stablest Conjecture must use a property that is special to partitions of sets into equal measures, since the conjecture is false in the unequal measure case.
This page was built for publication: Hyperstable Sets with Voting and Algorithmic Hardness Applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6411648)
