Chapter 11: Gaussian space and Invariance Principles

The final destination of this chapter is a proof of the following theorem due to Mossel, O’Donnell, and Oleszkiewicz [MOO05a,MOO10], first mentioned in Chapter 5.25:

Majority Is Stablest Theorem Fix $\rho \in (0,1)$. Let $f : \{-1,1\}^n \to [-1,1]$ have $\mathop{\bf E}[f] = 0$. Then, assuming $\mathbf{MaxInf}[f] \leq \epsilon$, or more generally that $f$ [...]

Chapter 10: Advanced hypercontractivity

In this chapter we complete the proof of the Hypercontractivity Theorem for uniform $\pm 1$ bits. We then generalize the $(p,2)$ and $(2,q)$ statements to the setting of arbitrary product probability spaces, proving the following:

The General Hypercontractivity Theorem Let $(\Omega_1, \pi_1), \dots, (\Omega_n, \pi_n)$ be finite probability spaces, in each of which [...]

Chapter 9: Basics of hypercontractivity

In 1970, Bonami proved the following central result:

The Hypercontractivity Theorem Let $f : \{-1,1\}^n \to {\mathbb R}$ and let ${1 \leq p \leq q \leq \infty}$. Then $\|\mathrm{T}_\rho f\|_q \leq \|f\|_p$ for $0 \leq \rho \leq \sqrt{\tfrac{p-1}{q-1}}$.

[...]

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: Property testing, PCPPs, and CSPs

In this chapter we study several closely intertwined topics: property testing, probabilistically checkable proofs of proximity (PCPPs), and constraint satisfaction problems (CSPs). All of our work will be centred around the task of testing whether an unknown boolean function is a dictator. We begin by extending the BLR Test to give a $3$-query property testing [...]

Chapter 6: Pseudorandomness and ${\mathbb F}_2$-polynomials

In this chapter we discuss various notions of pseudorandomness for boolean functions; by this we mean properties of a fixed boolean function which are in some way characteristic of randomly chosen functions. We will see some deterministic constructions of pseudorandom probability density functions with small support; these have algorithmic application in the field of derandomization. [...]

Chapter 5: Majority and threshold functions

This chapter is devoted to linear threshold functions, their generalization to higher degrees, and their exemplar the majority function. The study of LTFs leads naturally to the introduction of the Central Limit Theorem and Gaussian random variables — important tools in analysis of boolean functions. We will first use these tools to analyze [...]

Chapter 4: DNF formulas and small-depth circuits

In this chapter we investigate boolean functions representable by small DNF formulas and constant-depth circuits; these are significant generalizations of decision trees. Besides being natural from a computational point of view, these representation classes are close to the limit of what complexity theorists can “understand” (e.g., prove explicit lower bounds for). One reason [...]

Chapter 3: Spectral structure and learning

One reasonable way to assess the “complexity” of a boolean function is in terms how complex its Fourier spectrum is. For example, functions with sufficiently simple Fourier spectra can be efficiently learned from examples. This chapter will be concerned with understanding the location, magnitude, and structure of a boolean function’s Fourier spectrum.

Chapter 2: Basic concepts and social choice

In this chapter we introduce a number of important basic concepts including influences and noise stability. Many of these concepts are nicely motivated using the the language of social choice. The chapter is concluded with Kalai’s Fourier-based proof of Arrow’s Theorem.