
I’m happy to announce that the book is very nearly completed. In fact, you can preorder a copy now, either directly from Cambridge University Press, or from Amazon (currently with a 10% discount). If all goes well, the book will become physically available at the end of May. Fairly soon thereafter I will also make a pdf “final draft” version freely available here at the website.
In the meantime, I will continue to serialize the final chapter (Chapter 11) as usual over the next month. In fact, I had to trim and glue together the planned Chapters 11 and 12. Also, as mentioned earlier, I dropped a chapter on Additive Combinatorics that would have gone between Chapters 8 and 9, although its “highlight”, Sanders’s Theorem, is here on the blog. Oh well, I had to wrap this project up at some point; at least you’ll have an idea of what will be in the 2nd Edition.
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$ has no $(\epsilon,\epsilon)$notable coordinates, \[ \mathbf{Stab}_\rho[f] \leq 1 – \tfrac{2}{\pi} \arccos \rho + o_\epsilon(1). \]
Continue reading Chapter 11: Gaussian space and Invariance Principles
In Chapter 8.4 we described the problem of “threshold phenomena” for monotone functions $f : \{1,1\}^n \to \{1,1\}$.
Continue reading §10.5: Highlight: General sharp threshold theorems
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 when $\lambda = 1/n^{\Theta(1)}$.
Continue reading §10.4: More on randomization/symmetrization
In this section we will collect some applications of the General Hypercontractivity Theorem, including generalizations of the facts from Section 9.5.
Continue reading §10.3: Applications of general hypercontractivity
Let’s now study hypercontractivity for general random variables. By the end of this section we will have proved the General Hypercontractivity Theorem stated at the beginning of the chapter.
Continue reading §10.2: Hypercontractivity of general random variables
In this section we’ll prove the full Hypercontractivity Theorem for uniform $\pm 1$ bits stated at the beginning of Chapter 9:
Continue reading §10.1: The Hypercontractivity Theorem for uniform $\pm 1$ bits
In this chapter we complete the proof of the Hypercontractivity Theorem for uniform $\pm 1$ bits. We then generalize the $(p,2)$ and $(2,q)$ statements to the setting of arbitrary product probability spaces, proving the following:
The General Hypercontractivity Theorem Let $(\Omega_1, \pi_1), \dots, (\Omega_n, \pi_n)$ be finite probability spaces, in each of which every outcome has probability at least $\lambda$. Let $f \in L^2(\Omega_1 \times \cdots \times \Omega_n, \pi_1 \otimes \cdots \otimes \pi_n)$. Then for any $q > 2$ and $0 \leq \rho \leq \frac{1}{\sqrt{q1}} \cdot \lambda^{1/21/q}$, \[ \\mathrm{T}_\rho f\_q \leq \f\_2 \quad\text{and}\quad \\mathrm{T}_\rho f\_2 \leq \f\_{q'}. \] (In fact, the upper bound on $\rho$ can be slightly relaxed to the value stated in Theorem 17 of this chapter.)
Continue reading Chapter 10: Advanced hypercontractivity


Recent comments