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

Chapter 8: Generalized domains

So far we have studied functions $f : \{0,1\}^n \to {\mathbb R}$. What about, say, $f : \{0,1,2\}^n \to {\mathbb R}$? In fact, very little of what we’ve done so far depends on the domain being $\{0,1\}^n$; what it has mostly depended on is our viewing the domain as a product probability distribution. Indeed, much of analysis of boolean functions carries over to the case of functions $f : \Omega_1 \times \cdots \times \Omega_n \to {\mathbb R}$ where the domain has a product probability distribution $\pi_1 \otimes \cdots \otimes \pi_n$. There are two main exceptions: the “derivative” operator $\mathrm{D}_i$ does not generalize to the case when $|\Omega_i| > 2$ (though the Laplacian operator $\mathrm{L}_i$ does); and, the important notion of hypercontractivity (introduced in the next chapter) depends strongly on the probability distributions $\pi_i$.

In this chapter we focus on the case where all the $\Omega_i$’s are the same, as are the $\pi_i$’s. (This is just to save on notation; it will be clear that everything we do holds in the more general setting.) Important classic cases include functions on the $p$-biased hypercube (Section 4) and functions on abelian groups (Section 5). For the issue of generalizing the range of functions — e.g., studying functions $f : \{0,1,2\}^n \to \{0,1,2\}$ — see the exercises.