Standard Simplices and Pluralities are Not the Most Noise Stable

Steven Heilman, Elchanan Mossel, Joe Neeman

Abstract

For decades, the Standard Simplex Conjecture and the Plurality is Stablest Conjecture have suggested that certain highly symmetric partitions are the most robust to noise in Gaussian and discrete spaces. This research provides a definitive rebuttal to these conjectures in the general case. By employing a novel complex-analytic approach combined with variational calculus, the authors demonstrate that standard simplices and plurality functions are suboptimal whenever the partitions do not have equal measures. This result reveals a fundamental distinction between noise stability and classical isoperimetric problems, where optimal shapes typically maintain their geometric structure regardless of volume constraints.

Introduction

Noise stability is a central concept in probability theory, geometry, and theoretical computer science. It measures the likelihood that a partition of a space—whether a continuous Gaussian space or a discrete cube—remains unchanged when its input is subjected to small random perturbations.

In the case of a binary partition ($k=2$), the solution is well-understood: half-spaces are the most noise-stable sets. This is the geometric foundation of the "Majority is Stablest" theorem in social choice theory, which posits that a simple majority vote is the most robust against random errors. However, the problem becomes significantly more complex when the space is divided into $k \geq 3$ parts. For years, researchers conjectured that the optimal partitions would be Standard Simplices in Gaussian space and the Plurality function in discrete space. This paper investigates whether these natural generalizations of half-spaces and majority remain optimal when the partitions have unequal measures.

The Problem: Beyond Equal Measures

The "gap" addressed by this research is the assumption of symmetry. While the Standard Simplex and Plurality functions are intuitive candidates for optimality when each part has an equal share of the space (measure $1/k$), their performance in biased scenarios remained unproven. In classical isoperimetric theory, the "best" shape (such as a sphere) usually retains its fundamental geometric identity even as its volume changes. This paper asks if noise stability follows the same principle: does the simplex remain the most stable partition even when the "candidates" have unequal shares of the vote?

Methodology

The authors disprove the general conjectures using a combination of classical variational techniques and a sophisticated complex-analytic framework:

  1. First Variation (Normal Variation): The researchers applied a standard technique from the calculus of variations to "nudge" the boundaries of a partition. For a partition to be optimal, any small, volume-preserving perturbation must result in a decrease in noise stability, meaning the first derivative of the stability function must be zero at the boundary.
  2. Holomorphicity Argument: The key innovation lies in the treatment of the Ornstein-Uhlenbeck operator, which defines noise stability. The authors demonstrated that this operator becomes a holomorphic function when restricted to specific lines parallel to the facets of a simplicial cone.
  3. Contradiction via Analyticity: By establishing this holomorphicity, the authors proved that the "derivative equals zero" condition required for optimality cannot be satisfied across the entire boundary of a standard simplex unless the measures of all parts are perfectly equal. If the derivative is non-zero, a more stable partition can always be found by slightly perturbing the boundary.

Key Insights

Noise Stability vs. Surface Area

The findings highlight a critical rift between noise stability and classical geometry. Unlike surface area, which is a local property, noise stability is non-local—it involves an average over the entire space. This non-locality means that the optimal "shape" for noise stability is highly sensitive to the specific measures of the parts, changing its fundamental nature as soon as the volumes are biased.

The "Equal Measure" Exception

The paper clarifies that the original conjectures might still hold for the specific case where every part has a measure of exactly $1/k$. However, the proof demonstrates that any potential validation of those conjectures must rely strictly on that equality. This is a departure from the $k=2$ case, where half-spaces remain optimal regardless of the measure.

Results and Implications

  • Theorem 2.6 (Gaussian Space): The authors prove that for any $k \geq 3$ and any noise level $\rho \neq 0$, if the measures of the parts are not all equal, the standard simplex partition is not the most noise stable.
  • Corollary 2.9 (Discrete Space): In the context of voting theory, this implies that in a biased three-candidate election, the Plurality function is not the most noise-stable low-influence voting rule. There exists an alternative, currently unidentified function that provides greater robustness to noise.
  • Bilinear Stability: To illustrate how far the optimal solution can deviate from a simplex, the authors provide a specific example (Proposition 2.10) where parallel half-spaces outperform simplices in terms of stability.

Conclusion and Future Directions

This research serves as a significant "negative" result, successfully narrowing the search for optimal partitions by eliminating the most obvious candidates. While the paper proves that standard simplices and pluralities are not the optimizers in biased cases, it leaves several questions open:

  1. Identifying the Optimizer: The actual partitions that achieve maximum noise stability in the unequal measure case remain unknown.
  2. The $1/k$ Case: The conjectures for perfectly equal measures were not disproven here and remain a subject of intense study in the field.
  3. Constructive Algorithms: The proof is non-constructive; while it guarantees a better partition exists, it does not provide an algorithm to generate the most stable partition for arbitrary measures.

By breaking the assumption that symmetry implies stability, this work forces a re-evaluation of how we understand robustness in high-dimensional spaces.

Summary updated

BibTeX
@inproceedings{heilman2015standard,
  author = {Steven Heilman and Elchanan Mossel and Joe Neeman},
  title = {{Standard Simplices and Pluralities are Not the Most Noise Stable}},
  booktitle = {ITCS},
  year = {2015},
  doi = {10.1145/2688073.2688076},
}
Figure