§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 when $\lambda = 1/n^{\Theta(1)}$.
Continue reading §10.4: More on randomization/symmetrization

§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.
Continue reading §10.3: Applications of general hypercontractivity

§10.2: Hypercontractivity of general random variables

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

§10.1: The Hypercontractivity Theorem for uniform $\pm 1$ bits

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

Chapter 10: Advanced hypercontractivity

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{q-1}} \cdot \lambda^{1/2-1/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

Chapter 9 notes

The history of the Hypercontractivity Theorem is complicated.
Continue reading Chapter 9 notes

Chapter 9 exercises

Continue reading Chapter 9 exercises

§9.6: Highlight: The Kahn–Kalai–Linial Theorem

Recalling the social choice setting of Chapter 2.5, consider a $2$-candidate, $n$-voter election using a monotone voting rule $f : \{-1,1\}^n \to \{-1,1\}$. We assume the impartial culture assumption (that the votes are independent and uniformly random), but with a twist: one of the candidates, say $b \in \{-1,1\}$, is able to secretly bribe $k$ voters, fixing their votes to $b$. (Since $f$ is monotone, this is always the optimal way for the candidate to fix the bribed votes.) How much can this influence the outcome of the election?
Continue reading §9.6: Highlight: The Kahn–Kalai–Linial Theorem

§9.5: Applications of hypercontractivity

With the $(2,q)$- and $(p,2)$-Hypercontractivity Theorems in hand, let’s revisit some applications we saw in Sections 1 and 2.
Continue reading §9.5: Applications of hypercontractivity

§9.4: Two-function hypercontractivity and induction

At this point we have established that if $f : \{-1,1\} \to {\mathbb R}$ then for any $p \leq 2 \leq q$, \[ \|\mathrm{T}_{\sqrt{p-1}} f\|_2 \leq \|f\|_p, \qquad \|\mathrm{T}_{1/\sqrt{q-1}} f\|_q \leq \|f\|_2. \] We would like to extend these facts to the case of general $f : \{-1,1\}^n \to {\mathbb R}$; i.e., establish the $(p,2)$- and $(2,q)$-Hypercontractivity Theorems stated at the beginning of the chapter. A natural approach is induction.
Continue reading §9.4: Two-function hypercontractivity and induction