§9.4: Two-function hypercontractivity and induction

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{p-1}} f\|_2 \leq \|f\|_p, \qquad \|\mathrm{T}_{1/\sqrt{q-1}} 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)$- [...]

§9.3: $(2,q)$- and $(p,2)$-hypercontractivity for a single bit

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.


§9.2: Small subsets of the hypercube are noise-sensitive

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:2-4-hypercon-k} \|\mathrm{T}_{1/\sqrt{3}} f^{=k}\|_4 = \tfrac{1}{\sqrt{3}^k} \|f^{=k}\|_4 \leq \|f^{=k}\|_2. \end{equation}


§9.1: Low-degree polynomials are reasonable

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

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

§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}, [...]

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


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


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


§8.1: Fourier bases for product spaces

We will now begin to discuss functions on (finite) product probability spaces.