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

[...]

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

[...]

§7.1: Dictator testing

In Chapter 1.6 we described the BLR property testing algorithm: given query access to an unknown function $f : \{0,1\}^n \to \{0,1\}$, this algorithm queries $f$ on a few random inputs and approximately determines whether $f$ has the property of being linear over ${\mathbb F}_2$. The field of property testing for boolean functions is concerned [...]

§6.5: Highlight: Fooling ${\mathbb F}_2$-polynomials

Recall that a density $\varphi$ is said to be $\epsilon$-biased if its correlation with every ${\mathbb F}_2$-linear function $f$ is at most $\epsilon$ in magnitude. In the lingo of pseudorandomness, one says that $\varphi$ fools the class of ${\mathbb F}_2$-linear functions:

[...]

§6.4: Applications in learning and testing

In this section we describe some applications of our study of pseudorandomness.

[...]