
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.
Continue reading §9.4: Twofunction hypercontractivity and 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.
Continue reading §9.3: $(2,q)$ and $(p,2)$hypercontractivity for a single bit
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}
Continue reading §9.2: Small subsets of the hypercube are noisesensitive
As anyone who has worked in probability knows, a random variable can sometimes behave in rather “unreasonable” ways. It may be never close to its expectation. It might exceed its expectation almost always, or almost never. It might have finite $1$st, $2$nd, and $3$rd moments, but an infinite $4$th moment. All of this poor behaviour can cause a lot of trouble — wouldn’t it be nice to have a class of “reasonable” random variables?
Continue reading §9.1: Lowdegree polynomials are reasonable
In 1970, Bonami proved the following central result:
The Hypercontractivity Theorem Let $f : \{1,1\}^n \to {\mathbb R}$ and let ${1 \leq p \leq q \leq \infty}$. Then $\\mathrm{T}_\rho f\_q \leq \f\_p$ for $0 \leq \rho \leq \sqrt{\tfrac{p1}{q1}}$.
Continue reading Chapter 9: Basics of hypercontractivity
The origins of the orthogonal decomposition described in Section 3 date back to the work of Hoeffding [Hoe48] (see also [vMis47]).
Continue reading Chapter 8 notes
A decision tree $T$ for $f : \{1,1\}^n \to \{1,1\}$ can be thought of as a deterministic algorithm which, given adaptive query access to the bits of an unknown string $x \in \{1,1\}^n$, outputs $f(x)$. E.g., to describe a natural decision tree for $f = \mathrm{Maj}_3$ in words: “Query $x_1$, then $x_2$. If they are equal, output their value; otherwise, query and output $x_3$.” For a worstcase input (one where $x_1 \neq x_2$) this algorithm has a cost of $3$, meaning it makes $3$ queries. The cost of the worstcase input is the depth of the decision tree.
Continue reading §8.6: Highlight: Randomized decision tree complexity
The previous section covered the case of $f \in L^2(\Omega^n, \pi^{\otimes n})$ with $\Omega = 2$; there, we saw it could be helpful to look at explicit Fourier bases. When $\Omega \geq 3$ this is often not helpful, especially if the only “operation” on the domain is equality. For example, if $f : \{\mathsf{Red}, \mathsf{Green}, \mathsf{Blue}\}^n \to {\mathbb R}$ then it’s best to just work abstractly with the orthogonal decomposition. However if there is a notion of, say, “addition” in $\Omega$ then there is a natural, canonical Fourier basis for $L^2(\Omega, \pi)$ when $\pi$ is the uniform distribution.
Continue reading §8.5: Abelian groups


Recent comments