
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$ [...]
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 [...]
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{p1}{q1}}$.
[...]
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 [...]
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 [...]
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. [...]
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 [...]
In this chapter we investigate boolean functions representable by small DNF formulas and constantdepth 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 [...]
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.
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 Fourierbased proof of Arrow’s Theorem.


Recent comments