The Majority Is Stablest Theorem (to be proved at the end of this section) was originally conjectured in 2004 [KKMO04,KKMO07]. The motivation came from studying the approximability of the MaxCut CSP.
[...]


The Majority Is Stablest Theorem (to be proved at the end of this section) was originally conjectured in 2004 [KKMO04,KKMO07]. The motivation came from studying the approximability of the MaxCut CSP. [...] In Chapter 1.6 we described the BLR property testing algorithm: given query access to an unknown function $f : \{0,1\}^n \to \{0,1\}$, this algorithm queries $f$ on a few random inputs and approximately determines whether $f$ has the property of being linear over ${\mathbb F}_2$. The field of property testing for boolean functions is concerned [...] When there are just $2$ candidates, the majority function possesses all of the mathematical properties that seem desirable in a voting rule (e.g., May’s Theorem and Theorem 32). Unfortunately, as soon as there are $3$ (or more) candidates the problem of social choice becomes much more difficult. For example, suppose we have candidates $a$, [...] 

Copyright © 2015 Ryan O'Donnell  All Rights Reserved 
Recent comments