§2.3: Total influence

A very important quantity in the analysis of a boolean function is the sum of its influences.

Definition 26 The total influence of $f : \{-1,1\}^n \to {\mathbb R}$ is defined to be \[ \mathbf{I}[f] = \sum_{i=1}^n \mathbf{Inf}_i[f]. \]


§2.2: Influences and derivatives

Given a voting rule $f : \{-1,1\}^n \to \{-1,1\}$ it’s natural to try to measure the “influence” or “power” of the $i$th voter. One can define this to be the “probability that the $i$th vote affects the outcome”.


§2.1: Social choice functions

In this section we describe some rudiments of the mathematics of social choice, a topic studied by economists, political scientists, mathematicians, and computer scientists. The fundamental question in this area is how best to aggregate the opinions of many agents. Examples where this problem arises include citizens voting in an election, committees deciding on [...]

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