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*.

Sorry if I’ve misunderstood, but in the second example at the top of the page you’ve written:

“…Then f may represent a property of such graphs; e.g., f(G)=1 if and only if f is connected.”

Should this not read: “if and only if G is connected.”?

Whoops — bit of a blunder to have an error in the first paragraph! Thanks, I fixed it.

linguistic error:

I think it should be:

in a binary error-correcting*

instead of an binary error-correcting

Thanks! Right on page 1, too