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

• In circuit design, a boolean function may represent the desired behaviour of a circuit with $n$ inputs and one output.
• In graph theory, one can identify $v$-vertex graphs $G$ with length-$\binom{v}{2}$ strings indicating which edges are present. Then $f$ may represent a property of such graphs; e.g., $f(G) = 1$ if and only if $G$ is connected.
• In extremal combinatorics, a boolean function $f$ can be identified with a “set system” $\mathcal{F}$ on $[n] = \{1, 2, \dots, n\}$, where sets $X \subseteq [n]$ are identified with their $0$-$1$ indicators and $X \in \mathcal{F}$ if and only if $f(X) = 1$.
• In coding theory, a boolean function might be the indicator function for the set of messages in a binary error-correcting code of length $n$.
• In learning theory, a boolean function may represent a “concept” with $n$ binary attributes.
• In social choice theory, a boolean function can be identified with a “voting rule” for an election with two candidates named $0$ and $1$.

We will be quite flexible about how bits are represented. Sometimes we will use $\mathsf{True}$ and $\mathsf{False}$; sometimes we will use $-1$ and $1$, thought of as real numbers. Other times we will use $0$ and $1$, and these might be thought of as real numbers, as elements of the field ${\mathbb F}_2$ of size $2$, or just as symbols. Most frequently we will use $-1$ and $1$, so a boolean function will look like \begin{equation*} f : \{-1,1\}^n \to \{-1,1\}. \end{equation*} But we won’t be dogmatic about the issue.

We refer to the domain of a boolean function, $\{-1,1\}^n$, as the Hamming cube (or hypercube, $n$-cube, boolean cube, or discrete cube). The name “Hamming cube” emphasizes that we are often interested in the Hamming distance between strings $x, y \in \{-1,1\}^n$, defined by \begin{equation*} \mathrm{Dist}(x,y) = \#\{i : x_i \neq y_i\}. \end{equation*} Here we’ve used notation that will arise constantly: $x$ denotes a bit string and $x_i$ denotes its $i$th coordinate.

Suppose we have a problem involving boolean functions with the following two characteristics:

• the Hamming distance is relevant;
• you are counting strings, or the uniform probability distribution on $\{-1,1\}^n$ is involved.

These are the hallmarks of a problem for which analysis of boolean functions may help. Roughly speaking, this means deriving information about boolean functions by analyzing their Fourier expansion.