Noise Stability of Low Influence Boolean Functions

This direction is merged into another direction: conjecture-dependent hardness. Its last version stays readable and citable here.

Version 1 of 114 papers22 conceptsfrozen 2026-10-04

In social choice theory and computer science, a fundamental question arises: if every individual in a large group makes a slightly noisy or error-prone decision, which voting rule is most likely to produce a stable, consistent outcome?

The answer, formalized in the "Majority is Stablest" theorem, is the simple majority vote. This research direction explores why the majority function is the mathematical extremal for robustness against noise, provided that no single participant holds too much power.

The Problem of Influence and Noise

To understand noise stability, imagine a system where $n$ agents each provide a bit of information (e.g., a "Yes" or "No" vote). In a "noisy" environment, there is a small probability that any individual bit might be flipped. A function is considered noise stable if the output of the function remains the same even after some of its inputs are randomly corrupted.

However, stability is trivial if we allow a "dictator"—a single agent who determines the entire outcome. A dictator is perfectly stable (the outcome only flips if that one specific person's bit flips), but it fails to aggregate the collective will. Therefore, researchers like Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz focused on functions with low influence, where no single input has a disproportionate effect on the final result.

In their seminal work, Noise stability of functions with low influences: invariance and optimality, they proved that among all balanced functions where every variable has negligible influence, the majority function maximizes the correlation between the original and the noisy inputs.

The Invariance Principle

The technical engine behind these proofs is the Invariance Principle. This principle allows mathematicians to bridge the gap between discrete probability (flipping coins or bits) and continuous probability (Gaussian distributions).

As Ryan O’Donnell and Krzysztof Oleszkiewicz demonstrated in Noise stability of functions with low influences: Invariance and optimality (Annals 2010), low-influence polynomials behave essentially the same way whether their inputs are discrete bits or continuous Gaussian variables. This is powerful because high-dimensional Gaussian space has a clear geometric structure. In this continuous setting, the most "stable" way to partition space is using a half-space (a straight cut through the middle). When translated back to the discrete world of bits, this geometric "half-space" corresponds to the majority function.

From Individual Influence to Group Resilience

Recent work has expanded these bounds by relaxing the "low influence" requirement. While early theorems required that no single variable be powerful, newer research explores resilient functions—those where no small coalition of variables can significantly shift the outcome.

In Majority Is Asymptotically the Most Stable Resilient Function, it was shown that the same Gaussian stability bounds hold even if some variables have higher influence, provided the function's Fourier coefficients remain small. Elchanan Mossel further generalized this in Gaussian bounds for noise correlation of resilient functions, proving that noise stability is a fundamental property of any system where power is sufficiently distributed, regardless of whether that power is held by individuals or small groups.

Applications in Complexity and Social Choice

Why does this matter? The "Majority is Stablest" theorem isn't just about voting; it provides the mathematical "speed limit" for many computational problems.

  1. Hardness of Approximation: In theoretical computer science, these stability bounds are used to prove that certain problems, like Max-Cut, are "hard to approximate." If we could find an algorithm better than the current thresholds, it would effectively violate the stability limits established by the majority function.
  2. Social Choice Theory: Frederic Koehler and Elchanan Mossel applied these ideas to Arrow’s Impossibility Theorem in A Phase Transition in Arrow's Theorem. They found that while "fair" voting is mathematically difficult in independent populations, social correlation actually creates a "phase transition" where majority-style rules become exceptionally robust at producing rational group preferences.
  3. Collective Intelligence: Surprisingly, noise can be a benefit. Zhihuan Huang and colleagues in Decision Aggregation under Quantal Response argue that in groups with "bounded rationality" (stochastic, slightly irrational agents), majority voting serves as the optimal aggregator because it preserves weak information that a purely deterministic system might discard.

By mapping the discrete chaos of individual errors to the smooth geometry of Gaussian space, this research reveals that the majority rule is not just a convention, but a mathematical necessity for stability in distributed systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_noise_stability_of_low_influence_boolean_9218c37a,
  title = {Noise Stability of Low Influence Boolean Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/noise-stability-of-low-influence-boolean-functions/rdr_9218c37a20174d33b0edbc74b74ddf22},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_noise_stability_of_low_influence_boolean_9218c37a_v1,
  title = {Noise Stability of Low Influence Boolean Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/noise-stability-of-low-influence-boolean-functions/rdr_9218c37a20174d33b0edbc74b74ddf22/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}