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


In this section we will collect some applications of the General Hypercontractivity Theorem, including generalizations of the facts from Section 9.5. 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. 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:
Continue reading Chapter 10: Advanced hypercontractivity The history of the Hypercontractivity Theorem is complicated. 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? With the $(2,q)$ and $(p,2)$Hypercontractivity Theorems in hand, let’s revisit some applications we saw in Sections 1 and 2. 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{p1}} f\_2 \leq \f\_p, \qquad \\mathrm{T}_{1/\sqrt{q1}} 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. Although you can get a lot of mileage out of studying the $4$norm of random variables, it’s also natural to consider other norms. 

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