§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.


§11.6: The Invariance Principle

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$.)


§11.5: The Berry–Esseen Theorem

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

§11.4: Gaussian surface area and Bobkov’s Inequality

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 General-Volume Majority Is Stablest Theorem); in particular, it’s the special case arising from the limit $\rho \to 1^{-}$.


§11.3: Borell’s Isoperimetric Theorem

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.


§11.2: Hermite polynomials

Having defined the basic operators of importance for functions on Gaussian space, it’s useful to also develop the analogue of the Fourier expansion.


§11.1: Gaussian space and the Gaussian noise operator

We begin with a few definitions concerning Gaussian space.


§10.5: Highlight: General sharp threshold theorems

In Chapter 8.4 we described the problem of “threshold phenomena” for monotone functions $f : \{-1,1\}^n \to \{-1,1\}$.


§10.4: More on randomization/symmetrization

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

§10.3: Applications of general hypercontractivity

In this section we will collect some applications of the General Hypercontractivity Theorem, including generalizations of the facts from Section 9.5.