Chapter 9: Basics of hypercontractivity

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{p-1}{q-1}}$.

Continue reading Chapter 9: Basics of hypercontractivity

Chapter 8 notes

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

Chapter 8 exercises, continued

Continue reading Chapter 8 exercises, continued

Chapter 8 exercises

Continue reading Chapter 8 exercises

§8.6: Highlight: Randomized decision tree complexity

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 worst-case input (one where $x_1 \neq x_2$) this algorithm has a cost of $3$, meaning it makes $3$ queries. The cost of the worst-case input is the depth of the decision tree.
Continue reading §8.6: Highlight: Randomized decision tree complexity

§8.5: Abelian groups

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

§8.4: $p$-biased analysis

Perhaps the most common generalized domain in analysis of boolean functions is the case of the hypercube with “biased” bits.
Continue reading §8.4: $p$-biased analysis

§8.3: Orthogonal decomposition

In this section we describe a basis-free kind of “Fourier expansion” for functions on general product domains. We will refer to it as the orthogonal decomposition of $f \in L^2(\Omega^n, \pi^{\otimes n})$ though it goes by several other names in the literature: e.g., Hoeffding, Efron–Stein, or ANOVA decomposition.
Continue reading §8.3: Orthogonal decomposition

§8.2: Generalized Fourier formulas

In this section we will revisit a number of combinatorial/probabilistic notions and show that for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$, these notions have familiar Fourier formulas which don’t depend on the Fourier basis.
Continue reading §8.2: Generalized Fourier formulas

§8.1: Fourier bases for product spaces

We will now begin to discuss functions on (finite) product probability spaces.
Continue reading §8.1: Fourier bases for product spaces