[Computational Complexity] Majority is Stablest
Consider the following two voting schemes to elect a single candidate.
- Majority Vote.
- A Majority of Majorities (think an electoral college system with states of equal size).
In an upcoming FOCS paper, Elchanan Mossel, Ryan O'Donnell and Krzysztof Oleszkiewicz prove the "Majority is Stablest" conjecture that answers the above question and in fact shows that majority is the most stable function among balanced Boolean functions where each input has low influence. To understand this result we'll need to define the terms in the statement of the theorem.
- Balanced: A Boolean function is balanced if it has the same number of inputs mapping to zero as mapping to one.
- The influence of the ith variable is the expectation over a random input of the variance of setting the ith bit of the input randomly. The conjecture requires the influence of each variable to be bounded by a small constant.
- Stability: The noise stability of f is the expectation of f(x)f(y) where x and y are chosen independently.
Posted by Lance to Computational Complexity at 7/27/2005 04:35:00 PM