[...]


[...] [...] In this section we will collect some applications of the General Hypercontractivity Theorem, including generalizations of the facts from Section 9.5. [...] In this section we’ll prove the full Hypercontractivity Theorem for uniform $\pm 1$ bits stated at the beginning of Chapter 9: [...] [...] 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$ [...] With the $(2,q)$ and $(p,2)$Hypercontractivity Theorems in hand, let’s revisit some applications we saw in Sections 1 and 2. [...] An immediate consequence of the Bonami Lemma is that for any $f : \{1,1\}^n \to {\mathbb R}$ and $k \in {\mathbb N}$, \begin{equation} \label{eqn:24hyperconk} \\mathrm{T}_{1/\sqrt{3}} f^{=k}\_4 = \tfrac{1}{\sqrt{3}^k} \f^{=k}\_4 \leq \f^{=k}\_2. \end{equation} [...] In this section we prove two theorems about the degree$1$ Fourier weight of boolean functions: \[ \mathbf{W}^{1}[f] = \sum_{i=1}^n \widehat{f}(i)^2. \] [...] A very important quantity in the analysis of a boolean function is the sum of its influences. Definition 26 The total influence of $f : \{1,1\}^n \to {\mathbb R}$ is defined to be \[ \mathbf{I}[f] = \sum_{i=1}^n \mathbf{Inf}_i[f]. \] [...] 

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