Analysis of Boolean functions

In mathematics and theoretical computer science, analysis of Boolean functions is the study of real-valued functions on $\{0,1\}^{n}$ or $\{-1,1\}^{n}$ from a spectral perspective. The functions studied are often, but not always, Boolean-valued, making them Boolean functions. The area has found many applications in combinatorics, social choice theory, random graphs, and theoretical computer science, especially in hardness of approximation and property testing.

Basic concepts

Fourier expansion

Every real-valued function $f\colon \{-1,1\}^{n}\to \mathbb {R}$ has a unique expansion as a multilinear polynomial:

$f(x)=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}(x),\quad \chi _{S}(x)=\prod _{i\in S}x_{i}.$

This is the Hadamard transform of the function $f$, which is the Fourier transform in the group $\mathbb {Z} _{2}^{m}$. The coefficients ${\hat {f}}(S)$ are known as *Fourier coefficients*, and the entire sum is known as the *Fourier expansion* of $f$. The functions $\chi _{S}$ are known as *Fourier characters*, and they form an orthonormal basis for the space of all functions over $\{-1,1\}^{n}$, with respect to the inner product $\langle f,g\rangle =2^{-n}\sum _{x\in \{-1,1\}^{n}}f(x)g(x)$.

The Fourier coefficients can be calculated using an inner product:

${\hat {f}}(S)=\langle f,\chi _{S}\rangle .$

In particular, this shows that ${\hat {f}}(\emptyset )=\mathbb {E} [f]$. Parseval's identity states that

$\mathbb {E} [f^{2}]=\sum _{S}{\hat {f}}(S)^{2}.$

If we don't sum over $S=\emptyset$, then we get the variance of $f$.

References

• O'Donnell, Ryan (2014). Analysis of Boolean functions. Cambridge University Press. ISBN 978-1-107-03832-5.