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. [...] Let’s summarize the Variant Berry–Esseen Theorem and proof from the preceding section, using slightly different notation. (Specifically, we’ll rewrite $\boldsymbol{X}_i = a_i {\boldsymbol{x}}_i$ where $\mathop{\bf Var}[{\boldsymbol{x}}_i] = 1$, so $a_i = \pm \sigma_i$.) [...] The final destination of this chapter is a proof of the following theorem due to Mossel, O’Donnell, and Oleszkiewicz [MOO05a,MOO10], first mentioned in Chapter 5.25: Majority Is Stablest Theorem Fix $\rho \in (0,1)$. Let $f : \{1,1\}^n \to [1,1]$ have $\mathop{\bf E}[f] = 0$. Then, assuming $\mathbf{MaxInf}[f] \leq \epsilon$, or more generally that $f$ [...] In this section we prove two theorems about the degree$1$ Fourier weight of boolean functions: \[ \mathbf{W}^{1}[f] = \sum_{i=1}^n \widehat{f}(i)^2. \] [...] Majority is one of the more important functions in boolean analysis and its study motivates the introduction of one of the more important tools: the Central Limit Theorem (CLT). [...] 

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