Abstract
The "Majority Is Stablest" (MIST) theorem, established by Mossel, O'Donnell, and Oleszkiewicz (2005), asserts that for any two Boolean functions $f$ and $g$ with maximal influence $\tau$, their noisy inner product is bounded by the noisy inner product of Gaussian half-spaces of equivalent measures, up to an error $\varepsilon(\tau)$ that vanishes as $\tau \to 0$. This paper investigates whether the restrictive condition of low influences can be relaxed to the broader condition of vanishing Fourier coefficients, known as resilience. We answer this affirmatively, demonstrating that the Gaussian bounds hold for resilient functions. Furthermore, we show that if the noisy inner product of two functions exceeds the Gaussian bound, their Fourier supports for large coefficients must intersect. This work generalizes previous results and provides new structural insights into noise stability.
Introduction
In the study of Boolean functions, noise stability measures how the output of a function changes when its input is subjected to random perturbations. The Majority Is Stablest theorem is a cornerstone of this field, proving that among all functions where no single input variable has significant "influence," the Majority function is the most resistant to noise. This result has profound implications for social choice theory (e.g., Condorcet's paradox) and theoretical computer science (e.g., the hardness of the Unique Games problem).
However, the requirement of "low influence"—where the probability of a single bit flip changing the output is negligible—is a strong constraint. A more natural and general condition is "resilience." A function is considered resilient if its output remains largely unpredictable even if a small subset of its inputs is fixed. In Fourier terms, this corresponds to having vanishingly small Fourier coefficients for small sets of variables. This paper bridges the gap between these two concepts, proving that the stability properties of Majority extend to the broader class of resilient functions.
Methodological Framework
The proof utilizes a sophisticated sequence of mathematical reductions to translate discrete Boolean problems into the continuous Gaussian domain, where geometric bounds are more easily established.
1. Correlated Decision Trees
To handle multiple functions simultaneously, the author introduces "correlated decision trees." These trees expand variables across all functions $f$ and $g$ at once, allowing for a joint analysis of their structure. This technique is essential for proving the "intersection" property of Fourier supports.
2. Smoothing and Fourier Decomposition
The functions are subjected to a noise operator $T_\eta$, which "smooths" the function and makes it more analytically tractable. The author then employs the Steele-Efron-Stein decomposition to construct Fourier decision trees. These trees are designed to isolate and analyze the "large" Fourier coefficients that contribute most to the function's stability.
3. The Invariance Principle
Central to the proof is the Invariance Principle. This principle allows the behavior of functions on the discrete Boolean cube $\{-1, 1\}^n$ to be compared directly to functions on Gaussian space. By showing that resilient functions behave like Gaussian processes in the limit, the author can apply Gaussian noise stability bounds to the discrete case.
Key Theoretical Insights
Resilience as a Fundamental Property
The shift from influences to resilience is significant because resilience is a more robust measure of "spread out" behavior. In a social choice context, a resilient voting rule ensures that no small coalition of voters can bias the outcome on average, even if a specific voter might have high influence in certain rare configurations.
The Intersection Property
A primary contribution of this work is Theorem 1.5, which describes the structural requirements for functions that exceed Gaussian stability bounds. It states that if two functions $f$ and $g$ are more correlated than the Gaussian bound allows, they cannot be "cross-resilient." Specifically, their Fourier spectra must overlap; they must both depend heavily on the same small sets of input variables. This provides a structural characterization of functions that are "surprisingly" stable.
Strengthening Social Choice Theory
The paper provides a stronger version of the Arrow-Kalai theorem. In a three-candidate election, if the probability of a voting paradox is significantly lower than what the Majority rule achieves, the theorem now implies that at least two of the voting sub-functions must share a common structure, depending on the same small set of voters.
Results and Quantitative Bounds
The paper successfully generalizes MIST, proving that Gaussian bounds for noise correlation hold for any $(r, \alpha)$-resilient functions. This confirms that the "Majority Is Stablest" phenomenon is fundamentally a property of resilience.
While the existence of these bounds is proven, the author notes that the quantitative parameters are currently quite large. For a function to be considered stable under this framework, the required resilience $r$ is approximately $O(1/\epsilon^2 \tau)$, where $\tau$ is the influence threshold. These bounds involve exponential terms, suggesting that while the theory is sound, there is significant room for optimization in the constants.
Conclusion and Future Directions
By proving that Majority is the most stable resilient function, this work unifies concepts from additive combinatorics and noise stability. The most tantalizing future application lies in computational complexity. Many current hardness-of-approximation results are conditional on the Unique Games Conjecture (UGC). Because resilience is a weaker condition than low influence, the techniques developed here may eventually help convert these conditional results into standard NP-hardness results, potentially bypassing the need for the UGC in certain contexts. Additionally, the intersection property opens new avenues for exploring multi-function correlations in social choice and discrete geometry.
Summary updated