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

[...]

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

## Chapter 7 notes

The study of property testing was initiated by Rubinfeld and Sudan [RS96] and significantly expanded by Goldreich, Goldwasser, and Ron [GGR98]; the stricter notion of local testability was introduced (in the context of error-correcting codes) by Friedl and Sudan [FS95]. The first local tester for dictatorship was given by Bellare, Goldreich, and Sudan [BGS95,BGS98] (as [...]

[...]

## §7.4: Highlight: Håstad’s hardness theorems

In Theorem 36 we saw that it is $\mathsf{NP}$-hard to $(1-\delta_0, 1)$-approximate Max-E$3$Sat for some positive but inexplicit constant $\delta_0$. You might wonder how large $\delta_0$ can be. The natural limit here is $\frac18$ because there is a very simple algorithm which satisfies a $\frac78$-fraction of the constraints in any Max-E$3$Sat instance:

[...]

## §7.3: CSPs and computational complexity

This section is about the computational complexity of constraint satisfaction problems (CSPs), a fertile area of application for analysis of boolean functions. To study it we need to introduce a fair bit of background material; in fact, this section will mainly consist of definitions.

[...]

## §7.2: Probabilistically checkable proofs of proximity

In the previous section we saw that every subproperty of the dictatorship property has a $3$-query local tester. In this section we will show that any property whatsoever has a $3$-query local tester — if an appropriate “proof” is provided.

[...]