Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Majority is Stablest

Expand Messages
  • Lance
    Consider the following two voting schemes to elect a single candidate. Majority Vote. A Majority of Majorities (think an electoral college system with states
    Message 1 of 1 , Jul 27, 2005
      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.

      --
      Posted by Lance to Computational Complexity at 7/27/2005 04:35:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.