Chapter 1 notes

The Fourier expansion for real-valued boolean functions dates back to Walsh [Wal23] who introduced a complete orthonormal basis for $L^2([0,1])$ consisting of $\pm 1$-valued functions, constant on dyadic intervals.


Chapter 1 exercises


§1.6: Highlight: Almost linear functions and the BLR Test

In linear algebra there are two equivalent definitions of what it means for a function to be linear:

Definition 29 A function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ is linear if either of the following equivalent conditions hold:

$f(x+y) = f(x) + f(y)$ for all $x, y \in {\mathbb [...]

§1.5: Probability densities and convolution

For variety’s sake, in this section we write the Hamming cube as ${\mathbb F}_2^n$ rather than $\{-1,1\}^n$. In developing the Fourier expansion, we have generalized from boolean-valued boolean functions $f : {\mathbb F}_2^n \to \{-1,1\}$ to real-valued boolean functions $f : {\mathbb F}_2^n \to {\mathbb R}$. Boolean-valued functions arise more often in [...]

§1.4: Basic Fourier formulas

As we have seen, the Fourier expansion of $f : \{-1,1\}^n \to {\mathbb R}$ can be thought of as the representation of $f$ over the orthonormal basis of parity functions $(\chi_S)_{S \subseteq [n]}$. In this basis, $f$ has $2^n$ “coordinates”, and these are precisely the Fourier coefficients of $f$. The “coordinate” of $f$ [...]

§1.3: The orthonormal basis of parity functions

For $x \in \{-1,1\}^n$, the number $\chi_S(x) = \prod_{i \in S} x_i$ is in $\{-1,1\}$. Thus $\chi_S : \{-1,1\}^n \to \{-1,1\}$ is a boolean function; it computes the logical parity, or exclusive-or (XOR), of the bits $(x_i)_{i \in S}$. The parity functions play a special role in the analysis of boolean functions: [...]

§1.2: The Fourier expansion: functions as multilinear polynomials

The Fourier expansion of a boolean function $f : \{-1,1\}^n \to \{-1,1\}$ is simply its representation as a real, multilinear polynomial. (Multilinear means that no variable $x_i$ appears squared, cubed, etc.) For example, suppose $n = 2$ and $f = {\textstyle \min_2}$, the “minimum” function on $2$ bits:


§1.1: On analysis of boolean functions

This is a book about boolean functions, \begin{equation*} f : \{0,1\}^n \to \{0,1\}. \end{equation*} Here $f$ maps each length-$n$ binary vector, or string, into a single binary value, or bit. Boolean functions arise in many areas of computer science and mathematics. Here are some examples: