Boolean Fourier Analysis and Complexity Measures of Boolean Functions

Corresponds to advanced course, Lecture 2 Part 2 — Lecture 4. Every Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ has a unique expansion in the characters $\chi_S(x) = \prod_{i\in S}x_i$ — its Fourier expansion — which turns combinatorial questions about $f$ into analytic/linear-algebraic ones. Applies this immediately to coding theory: the BLR (Blum-Luby-Rubinfeld) linearity test checks whether a function is close to linear using only a few queries, via a slick Fourier-analytic proof — the prototype for local testability (checking a huge structure is almost-correct from a handful of samples) and, in the next note, for the PCP theorem itself. Local correctability and decodability push further: recovering a single coordinate (or a full message) correctly even from a corrupted codeword, using few queries. The Boolean hypercube $\{-1,1\}^n$, viewed as a graph (a specific Cayley graph), has explicit eigenvectors (the same Fourier characters) and eigenvalues, linking this analytic machinery directly to the spectral-graph-theory view of expanders in expander-graphs-fundamentals. Closes with the standard combinatorial complexity measures of a Boolean function — sensitivity, (Fourier) degree, and decision-tree complexity — and the (largely Fourier-driven) results relating them.

Outline (TODO — flesh out each)

• Introduction to Boolean Fourier analysis
• Codes, local testability, and the BLR linearity test
• Local correctability and local decodability
• Cayley graphs; the Boolean hypercube, its eigenvectors and eigenvalues
• Complexity measures of Boolean functions — sensitivity, degree, decision-tree complexity