Abstract: In this paper we derive tight bounds on the expected value of products of low influence functions defined on correlated probability spaces. The proofs are based on extending Fourier theory to an arbitrary number of correlated probability spaces, on a generalization of an invariance principle recently obtained with O’Donnell and Oleszkiewicz for multilinear polynomials with low influences and bounded degree and on properties of multi-dimensional Gaussian distributions.
Introduction
In the study of social choice theory and theoretical computer science, we often analyze functions $f(x_1, \dots, x_n)$ where the inputs are random variables. A critical property in these analyses is influence: a measure of how much changing a single input $x_i$ can alter the final output. Functions where no single coordinate has a disproportionate impact are termed "low influence" functions. These functions are central to understanding systems where collective behavior emerges from many individual, non-dictatorial components.
This paper addresses the challenge of noise correlation. Specifically, it investigates how functions behave when their inputs are correlated or subject to noise—for instance, when different voters in an election observe slightly different versions of the same information. While previous research provided tight bounds for the correlation of two functions, this work extends the framework to an arbitrary number of functions and correlated spaces, creating a robust bridge between discrete probability and continuous Gaussian geometry.
Theoretical Framework
The paper’s methodology is built upon three primary mathematical pillars that allow for the translation of discrete problems into a continuous, geometric context.
1. Generalized Fourier Theory
The author extends standard Fourier analysis to operate across multiple correlated probability spaces simultaneously. This is achieved through the Efron–Stein decomposition, which allows a function to be broken down into constituent parts based on subsets of its inputs. This decomposition is essential for isolating the effects of low-influence variables across complex, multi-variable systems.
2. The Invariance Principle
Building on the "Lindeberg strategy"—a method of switching discrete variables to Gaussian ones one by one—the paper proves a generalized Invariance Principle. It demonstrates that for low-influence functions, the joint distribution of several multilinear polynomials remains essentially unchanged whether the inputs are discrete (such as bits in a computer) or Gaussian (continuous variables). This principle is the "engine" of the paper, allowing discrete combinatorial problems to be treated as continuous ones.
3. Gaussian Isoperimetry
Once the problem is mapped into Gaussian space, the author utilizes geometric tools such as Borell’s inequality. This step transforms abstract probability questions into concrete geometric ones regarding the surface area and volume of shapes in high-dimensional space. By finding the extremal cases in this Gaussian environment, the author derives tight bounds that apply back to the original discrete functions.
Key Insights and Results
The "Majority is Most Predictable" Principle
A significant finding of this work is a variation of the "Majority is Stablest" theorem. The paper proves that if one only observes a random sample of votes, the Majority function is the most "predictable" among all possible low-influence voting schemes. Specifically, Theorem 1.1 establishes that for any low-influence function $f$, the probability of correctly predicting the outcome given a sample of voters is at most $\frac{2}{\pi} \arcsin \sqrt{\rho} + \epsilon$, a bound that the Majority function achieves.
Condorcet Paradoxes
The research provides new insights into the Condorcet paradox—a situation where collective preferences can be cyclic (e.g., a majority prefers A over B, B over C, and C over A). In elections with $k$ candidates, the paper proves that for any low-influence voting system, the probability of a "unique winner" (a Condorcet winner) vanishes as the number of candidates $k$ grows. The probability behaves according to the scale $k^{-1+o(1)}$.
Computational Complexity and CSPs
The bounds derived in this paper have profound implications for the "Hardness of Approximation" in computer science. The results were instrumental in subsequent work showing that for many Constraint Satisfaction Problems (CSPs), if the Unique Games Conjecture (UGC) holds, then simple random guessing is essentially the most effective polynomial-time algorithm possible. This suggests that for a wide class of hard problems, we cannot expect to find significantly better approximations than those provided by basic heuristics.
Discussion and Limitations
While the paper provides a powerful framework for noise correlation, it notes several areas for further refinement:
- The Low Influence Constraint: The tightest bounds are contingent on all coordinates having small influence. While a recursive argument (Proposition 1.16) is provided to handle functions with some influential coordinates by "fixing" certain variables, this aspect of the theory remains less developed than the low-influence case.
- Condorcet Tightness: There remains a small mathematical gap between the upper bound for Condorcet winners ($k^{-1+o(1)}$) and the specific behavior observed in the Majority function ($k^{-1-o(1)}$).
- Reliance on Conjectures: Many of the practical applications in computational complexity are conditional on the Unique Games Conjecture. As the UGC remains one of the most significant open problems in the field, the ultimate impact of these bounds on complexity theory depends on its eventual proof or disproof.
In conclusion, by establishing a rigorous link between discrete noise correlation and Gaussian geometry, this work provides a fundamental toolset for analyzing social choice, probability, and the limits of computation.
Summary updated