Abstract
Gaussian noise stability results have recently played an important role in proving results in hardness of approximation in computer science and in the study of voting schemes in social choice. We prove a new Gaussian noise stability result generalizing an isoperimetric result by Borell on the heat kernel and derive as applications:
- An optimality result for majority in the context of Condorcet voting.
- A proof of a conjecture on "cosmic coin tossing" for low influence functions. We also discuss a Gaussian noise stability conjecture which may be viewed as a generalization of the "Double Bubble" theorem and show that it implies:
- A proof of the "Plurality is Stablest Conjecture".
- That the Frieze-Jerrum SDP for MAX-q-CUT achieves the optimal approximation factor assuming the Unique Games Conjecture.
Introduction
The study of noise stability explores how sensitive a system's output is to small perturbations in its input. In high-dimensional geometry, this translates to finding partitions of space that minimize the "leakage" across boundaries when subjected to Gaussian noise. While C. Borell established in the 1980s that a half-space is the most stable partition for two correlated Gaussian variables, many modern problems in social choice and computer science involve multiple outcomes or candidates. This paper bridges the gap between these geometric foundations and discrete systems, proving new results that determine the optimality of voting schemes and the limits of computational approximation.
Theoretical Framework: Generalizing Gaussian Stability
The authors address two primary generalizations of classical noise stability:
- Multiple Inputs: Extending stability results to $k > 2$ correlated inputs.
- Multiple Partitions: Identifying the most stable way to divide space into $q > 2$ regions.
Exchangeable Gaussians Theorem (EGT)
The paper proves the Exchangeable Gaussians Theorem, which states that for any number of symmetrically correlated (exchangeable) Gaussian vectors, the half-space remains the optimal partition. This proof utilizes spherical rearrangements and the Riesz inequality to maintain geometric rigor across higher dimensions.
The Standard Simplex Conjecture (SSC)
A central theme is the "Standard Simplex Conjecture," which posits that the most stable partition of space into $q$ equal-volume parts is a Standard Simplex Partition. In a two-dimensional plane, this manifests as three lines meeting at 120-degree angles—reminiscent of the "peace sign." This conjecture is a Gaussian analogue to the "Double Bubble" theorem in geometry, which describes the shape of two joined soap bubbles that minimize surface area for a given volume.
Applications in Social Choice and Computer Science
By employing an Extended Invariance Principle, the authors translate these continuous geometric results into discrete settings. This principle allows results derived from smooth Gaussian distributions to be applied to "jagged" discrete domains like bit-strings or individual votes.
Optimality of Majority and Plurality
The research provides a mathematical justification for the prevalence of the Majority rule. In Condorcet voting, Majority is shown to be the most stable rule among all schemes where no single voter has disproportionate influence. Furthermore, if the Standard Simplex Conjecture holds, it proves the "Plurality is Stablest" conjecture, establishing Plurality as the optimal aggregation method for $q$ candidates.
Computational Complexity: MAX-q-CUT
The findings have significant implications for the MAX-q-CUT problem, which involves partitioning graph vertices into $q$ sets to maximize the number of edges between different sets. The paper shows that the SSC implies the Frieze-Jerrum Semidefinite Programming (SDP) algorithm achieves the optimal approximation ratio, assuming the validity of the Unique Games Conjecture (UGC).
Conclusion and Future Directions
While the paper successfully proves the EGT and establishes the profound consequences of the Standard Simplex Conjecture, the SSC itself remains a conjecture for the general case $q > 2$. Future work involves proving this geometric property directly and exploring settings beyond "low-influence" functions. Additionally, the computational results remain conditional on the Unique Games Conjecture, highlighting a deep link between high-dimensional geometry and the fundamental limits of computation.
Summary updated