Chapter 5 notes

Chow’s Theorem was proved by independently by Chow [Cho61] and by Tannenbaum [Tan61] in 1961; see also [Elg61].

[...]

Chapter 5 exercises, continued

[...]

Chapter 5 exercises

[...]

§5.5: Highlight: Peres’s Theorem

Theorem 14 says that if $f$ is an unbiased linear threshold function $f(x) = \mathrm{sgn}(a_1 x_1 + \cdots + a_n x_n)$ in which all $a_i$’s are “small” then the noise stability $\mathbf{Stab}_\rho[f]$ is at least (roughly) $\frac{2}{\pi} \arcsin \rho$. Rephrasing in terms of noise sensitivity, this means $\mathbf{NS}_\delta[f]$ is at most (roughly) $\tfrac{2}{\pi} \sqrt{\delta} [...]

§5.4: Degree-1 weight

In this section we prove two theorems about the degree-$1$ Fourier weight of boolean functions: \[ \mathbf{W}^{1}[f] = \sum_{i=1}^n \widehat{f}(i)^2. \]

[...]

§5.3: The Fourier coefficients of Majority

In this section we will analyze the Fourier coefficients of $\mathrm{Maj}_n$. In fact, we give an explicit formula for them in Theorem 16 below. But most of the time this formula is not too useful; instead, it’s better to understand the Fourier coefficients of $\mathrm{Maj}_n$ asymptotically as $n \to \infty$.

[...]

§5.2: Majority, and the Central Limit Theorem

Majority is one of the more important functions in boolean analysis and its study motivates the introduction of one of the more important tools: the Central Limit Theorem (CLT).

[...]

§5.1: Linear threshold functions and polynomial threshold functions

Recall from Chapter 2.1 that a linear threshold function (abbreviated LTF) is a boolean-valued function $f : \{-1,1\}^n \to \{-1,1\}$ that can be represented as \begin{equation} \label{eqn:generic-LTF} f(x) = \mathrm{sgn}(a_0 + a_1 x_1 + \cdots + a_n x_n) \end{equation} for some constants $a_0, a_1, \dots, a_n \in {\mathbb R}$.

[...]

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