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

Hiatus

The last video lecture for my CMU course on Analysis of Boolean Functions has just been posted. Except for responding to comments, the blog will be going on hiatus for a little while. Next semester I’ll post the final chapters of the book; there will be between 4 and 7 of them, depending on how much energy I have.

Happy holidays……..

CMU online course: Lecture 23 published

The video for Lecture 23 of the online course is available on the course web page.

CMU online course: Lecture 22 published

The video for Lecture 22 of the online course is available on the course web page.

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 in Exercise 8); it was later rediscovered by Parnas, Ron, and Samorodnitsky [PRS01,PRS02]. The relevance of Arrow’s Theorem to testing dictatorship was pointed out by Kalai [Kal02].
Continue reading Chapter 7 notes

CMU online course: Lecture 21 published

The video for Lecture 21 of the online course is available on the course web page.