## Chapter 10 exercises

Let $\boldsymbol{X}$ be a random variable and let $1 \leq r \leq \infty$. Recall that the triangle (Minkowski) inequality implies that for real-valued functions $f_1, f_2$, $\|f_1(\boldsymbol{X}) + f_2(\boldsymbol{X})\|_r \leq \|f_1(\boldsymbol{X})\|_r + \|f_2(\boldsymbol{X})\|_r.$ More generally, if $w_1, \dots, w_m$ are nonnegative reals summing to $1$ and $f_1, \dots, f_m$ are real functions [...]

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

[...]

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

[...]

## §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:

[...]

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

## Chapter 9 notes

The history of the Hypercontractivity Theorem is complicated.

[...]

[...]

## §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$ [...]