Introduction
In the study of Boolean functions and social choice theory, a fundamental question asks: "Which voting rule is most stable to noise?" The celebrated "Majority is Stablest" theorem (MIST) provides a definitive answer: among functions where no single voter holds disproportionate power—a condition known as "low influence"—the Majority function is the most stable.
However, the requirement of low influence is quite restrictive. In many practical scenarios, such as complex voting systems or hardness of approximation in computer science, we are more concerned with the underlying Fourier spectrum of a function than the power of individual variables. This paper addresses a long-standing open question: can we achieve the same powerful Gaussian noise correlation bounds if we relax the "low influence" requirement to a broader condition called "resilience"?
Defining Resilience
A function is considered "resilient" if the average value of the function does not change significantly even if a small coalition of coordinates is fixed. This is a more natural and often weaker condition than low influence. While a function might have a single influential variable (like a "dictator" in a small subset of the domain), it can still be resilient on average.
By shifting the focus from individual influences to resilience, the author argues that the Fourier transform is a more fundamental object for understanding noise stability. This work effectively bridges a gap between additive combinatorics, where obstructions to typical behavior are defined by Fourier norms, and noise stability theory, where they have traditionally been defined by high influences.
Methodology: The Decision Tree Approach
The primary technical innovation of this paper is the application of the Decision Tree method, specifically through two new variants designed to bridge the gap between resilience and low-influence theory:
- Correlated Decision Trees: These are used for the general case involving multiple functions. The tree "expands" variables across all functions simultaneously until the majority of the resulting "leaves" (sub-functions) exhibit low influence. Once this state is reached, existing Gaussian bounds from 2008 and 2010 can be applied.
- Fourier Decision Trees: These are employed to analyze the interaction between two functions. This technique identifies whether two functions share a "common structure" in their Fourier supports, which is critical for determining their correlation.
The overall proof strategy involves taking a "smoothed" version of a function and demonstrating that if it is resilient, a decision tree can decompose it into pieces that are mostly low-influence, allowing for the application of established Gaussian machinery.
Key Results and Insights
Generalization of Majority is Stablest
The paper’s central result, Theorem 1.4, proves that Gaussian bounds for noise correlation hold for any functions that are $(r, \alpha)$-resilient. This confirms that the logic of "Majority is Stablest" applies to a much broader class of functions than previously understood, moving beyond the strict low-influence constraint.
Fourier Interaction and Correlation
In Theorem 1.5, the author establishes that if the "noisy inner product" of two functions (a measure of how much they agree after random input bit-flips) exceeds the theoretical Gaussian limit, they must share a common influential structure. Specifically, their large Fourier coefficients must intersect. This provides a structural explanation for why certain functions appear more correlated than threshold functions like Majority.
Strengthening the Arrow-Kalai Theorem
The research provides a significant strengthening of the Arrow-Kalai Theorem in social choice theory. It demonstrates that in a three-candidate election, if the probability of a "voting paradox" (such as Condorcet's paradox) is lower than what the Majority rule achieves, then at least two of the constituent voting functions must be correlated with a small, shared set of voters.
Limitations and Future Directions
While the theoretical results are robust, the author notes that the current quantitative bounds for the resilience parameters ($r$ and $\alpha$) are "heavy." Specifically, $r$ is exponential and $\alpha$ is doubly exponential in terms of the error $\epsilon$. Refining these into polynomial-like bounds remains a primary goal for future research.
Furthermore, the paper hints at a major application in computational complexity: the potential to transform "Unique Games Hardness" results into "NP-hardness" results. Unique Games proofs often rely on the existence of a single influential variable, whereas NP-hardness proofs can sometimes utilize the broader "large Fourier coefficient" condition established here. However, the author acknowledges that this is a challenging direction requiring further development of the "outer verifier" components of these proofs.
Summary updated