Why are some logic functions easy for AI to learn, while others are nearly impossible? The answer lies in the Fourier Spectrum.
Standard logic uses {0, 1}. Fourier analysis prefers {-1, +1}. The map is \(\chi(b) = (-1)^b\): bit 0 becomes +1, bit 1 becomes −1. This translation turns logical rules into algebraic equations, making Walsh functions the orthonormal basis for all Boolean functions.
Adjust variables, select a function, or build your own.
The definitions that make the spectrum meaningful.
The algorithm that computes all 2ⁿ Fourier coefficients in O(n·2ⁿ) time.
Influence of variable \(i\): \(\mathbf{Inf}_i[f] = \sum_{S \ni i} \hat{f}(S)^2\). Poincaré inequality: \(\mathbf{Var}[f] \leq \sum_i \mathbf{Inf}_i[f]\).
The Linial-Mansour-Nisan (1993) theorem: AC⁰ circuits have spectra concentrated on low-degree coefficients. Formally, \(\sum_{|S|>k} \hat{f}(S)^2 \leq \varepsilon\) for small \(k\). Functions like PARITY violate this — their mass lives entirely at maximum degree.
Train a 2-layer network on the selected Boolean function. Watch the loss reflect the function's Fourier complexity.
AND, OR, MAJORITY, DICTATOR concentrate mass on degree-1 coefficients. A single perceptron finds these gradients immediately — no hidden layers required.
PARITY places all its mass on the degree-n coefficient. It looks like pure noise to a perceptron — the gradient signal is zero at initialization. Requires exponential depth or width to learn.
Fourier analysis gives an X-ray of a Boolean function's computational complexity before training begins. Spectral mass concentration predicts learnability across model families.
Ryan O'Donnell. Cambridge University Press, 2014. arXiv:2105.10386
The definitive graduate-level textbook. Chapters 1–3 cover the Fourier expansion, Walsh characters, and spectral concentration theorems visualized in this app. The free online edition includes exercises that pair naturally with the interactive presets.
N. Linial, Y. Mansour, N. Nisan. JACM, 40(3):607–620, 1993. DOI:10.1145/174130.174138
The foundational paper connecting Boolean Fourier analysis to PAC learning theory. Proves that AC⁰ circuits have spectra concentrated on low-degree coefficients — the pattern visible when selecting TRIBES or AND and observing cool-colored bars dominating the spectrum.
Hao Huang. Annals of Mathematics, 190(3):949–955, 2019. DOI:10.4007/annals.2019.190.3.6
Huang's two-page proof resolved a three-decade-old conjecture relating sensitivity to block sensitivity. Demonstrates that Fourier analysis on the Boolean cube remains a fertile source of breakthrough results. The INNER PRODUCT preset attains the conjectured bound with equality.