Fourier analysis on the Boolean cube

Summary

Fourier analysis on the Boolean cube studies functions $f \colon \set{-1, 1}^n \to \R$ as combinations of parity functions. The parity function of a subset $S$ of $\set{1, \dots, n}$ is $\chi_S(x) = \prod_{i \in S} x_i$. The parity functions are the characters of the group $(\Z/2\Z)^n$, so this is Fourier analysis on a finite abelian group. The coefficients are given by the Walsh–Hadamard transform. It is a main tool for Boolean functions in theoretical computer science, social choice, learning theory and hardness of approximation. Notions such as influence, noise sensitivity and the degree of a function are read off from the Fourier coefficients.