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$.) [...] Now that we’ve built up some results concerning Gaussian space, we’re motivated to try reducing problems involving Boolean functions to problems involving Gaussian functions. The key tool for this is the Invariance Principle, discussed at the beginning of the chapter. As a warmup, this section is devoted to proving (a form of) the Berry–Esseen [...] This section is devoted to studying the Gaussian Isoperimetric Inequality. This inequality is a special case of the Borell Isoperimetric Inequality (and hence also a special case of the GeneralVolume Majority Is Stablest Theorem); in particular, it’s the special case arising from the limit $\rho \to 1^{}$. [...] If we believe that the Majority Is Stablest Theorem should be true, then we also have to believe in its “Gaussian special case”. Let’s see what this Gaussian special case is. [...] Having defined the basic operators of importance for functions on Gaussian space, it’s useful to also develop the analogue of the Fourier expansion. [...] In Chapter 8.4 we described the problem of “threshold phenomena” for monotone functions $f : \{1,1\}^n \to \{1,1\}$. [...] In Section 3 we collected a number of consequences of the General Hypercontractivity Theorem for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$. All of these had a dependence on “$\lambda$”, the least probability of an outcome under $\pi$. This can sometimes be quite expensive; for example, the KKL Theorem and its consequence Theorem 28 are trivialized [...] In this section we will collect some applications of the General Hypercontractivity Theorem, including generalizations of the facts from Section 9.5. [...] 

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