Majority is Stablest

Consider the following two voting schemes to elect a single candidate.

1. Majority Vote.
2. A Majority of Majorities (think an electoral college system with states of equal size).

Which of these voting systems are more stable, i.e., less likely to be affected by flipping a small number of votes?

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.

The majority is stablest conjecture has applications for approximation via the unique games conjecture.