§11.7: Highlight: Majority Is Stablest Theorem

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 Max-Cut CSP.


§7.1: Dictator testing

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 [...]

§2.5: Highlight: Arrow’s Theorem

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$, [...]