Noise stability of functions with low influences: Invariance and optimality

Elchanan Mossel, Ryan O’Donnell, Krzysztof OleszkiewiczAnnals 2010 · DOI

Abstract

In this paper, we study functions with low influences on product probability spaces. These are functions $f: \Omega^n \to \mathbb{R}$ where the influence of each coordinate $i$, defined as $E[Var_i[f]]$, is small compared to the total variance $Var[f]$. The analysis of Boolean functions $f: \{-1, 1\}^n \to \{-1, 1\}$ with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics.

Introduction

In the fields of theoretical computer science and social choice theory, researchers frequently analyze functions that aggregate many individual inputs—such as votes in an election or bits in a computational circuit—to produce a single output. A critical property of these functions is their noise stability: how likely is the output to remain the same if the input data is slightly corrupted by random noise?

The Annals of Mathematics logo, where this seminal work was published.

A central challenge in this area involves functions with low influences. In such functions, no single input variable has a disproportionate impact on the final outcome; there are no "dictators." For decades, it was conjectured that among all such "fair" or "balanced" functions, the Majority function (where the output is determined by the most frequent input) is the most stable against noise. This became known as the "Majority Is Stablest" conjecture. However, proving this was historically difficult because the discrete Boolean space of bits is mathematically "jagged" and lacks the smooth properties of continuous spaces like the Gaussian distribution. This paper bridges that gap by introducing a formal way to translate results between these two worlds.

The Nonlinear Invariance Principle

The core methodological contribution of this work is the Nonlinear Invariance Principle. This principle provides a quantitative tool to show that the distribution of a low-influence polynomial remains essentially unchanged whether its inputs are discrete bits or continuous Gaussian variables.

Generalizing the Central Limit Theorem

The classic Central Limit Theorem (CLT) states that the sum of many independent, identically distributed variables (essentially a degree-1 polynomial) tends toward a Gaussian distribution. The authors extend this logic to multilinear polynomials of any fixed degree $d$. They demonstrate that as long as the influence of each variable is small, the "shape" of the function's output distribution is invariant to the specific distribution of the independent input variables.

Lindeberg’s Method and Hypercontractivity

To prove this, the authors adapted Lindeberg’s method, a classic technique for proving the CLT. The method involves replacing discrete variables with Gaussian ones one-by-one. By showing that the error introduced at each step is negligible when influences are low, they prove the overall distribution stays stable.

To maintain control over the "tails" of these distributions and ensure the error bounds were explicit, the authors employed tools from functional analysis, specifically hypercontractive ensembles. These tools allow for the comparison of different norms of polynomials, ensuring that the probability of extreme values (outliers) is well-behaved.

Smoothing and Truncation

Real-world functions often have infinite degree when expanded into Fourier series. To handle this, the authors introduced a smoothing operator ($T_\rho$). This operator slightly "blurs" the function, effectively damping high-degree terms. This allows the function to be approximated by a low-degree polynomial without losing the essence of the function's behavior, making it amenable to the invariance principle.

The Gaussian Bridge and Key Insights

The most profound insight of the paper is the creation of a "Gaussian Bridge." For functions where no single variable is too powerful, the complex geometry of the $n$-dimensional Boolean cube behaves remarkably like the smooth geometry of Gaussian space.

This realization allows researchers to solve difficult problems in the "smooth" Gaussian world—where calculus and geometric tools are readily available—and then automatically apply those solutions back to the "pixelated" world of computer science.

Furthermore, the paper confirms that the Majority function is an extremal case. It is not merely a common voting rule; it represents a mathematical boundary. It is the most stable possible method for aggregating information under the constraint that no single participant holds too much power.

Major Results and Implications

The theoretical framework established in this paper led to several landmark results:

  1. Proof of "Majority Is Stablest": The authors proved that for any balanced, low-influence function $f$, its noise stability is at most $(2/\pi) \arcsin \rho + \epsilon$. This precisely matches the stability of the Majority function in the limit.
  2. Optimality of Max-Cut: This proof had immediate, transformative consequences for computational complexity. It showed that if the Unique Games Conjecture (UGC) holds, then the Goemans-Williamson algorithm—which achieves an approximation ratio of approximately 0.878—is the absolute best any polynomial-time algorithm can do for the Max-Cut problem. This provided the first evidence that certain "hard" problems have fundamental algorithmic limits tied to noise stability.
  3. Social Choice Theory: They proved the "It Ain’t Over Till It’s Over" conjecture. In a fair, large-scale election, revealing a random fraction of the votes is unlikely to determine the winner with certainty, provided no single voter is too influential. This formalizes the intuition that large, fair systems are inherently unpredictable until most data is in.

Limitations and Future Directions

While the paper is a cornerstone of modern discrete Fourier analysis, it leaves open several avenues. The most significant is the dependency on the Unique Games Conjecture. While "Majority Is Stablest" is now a proven theorem, its implication regarding the optimality of algorithms like Max-Cut relies on the UGC, which remains one of the most significant unsolved problems in theoretical computer science.

Additionally, the results are sensitive to the specific definition of "influence" used. Future research continues to explore how these invariance principles behave under different constraints, such as for functions that are not perfectly balanced or for different types of noise models. Finally, while the paper provides explicit error bounds, subsequent work in cryptography and learning theory has focused on sharpening these bounds for more practical applications.

Summary updated

Abstract

In this paper we study functions with low influences on product probability spaces. These are functions f W 1 n ! that have EOEVar i OEf small compared to VarOEf for each i . The analysis of boolean functions f W f 1; 1g n ! f 1; 1g with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics.
BibTeX
@article{mossel2010noise,
  author = {Elchanan Mossel and Ryan O’Donnell and Krzysztof Oleszkiewicz},
  title = {{Noise stability of functions with low influences: Invariance and optimality}},
  journal = {Annals},
  year = {2010},
  doi = {10.4007/annals.2010.171.295},
}
Figure