Opening Boolean Fourier Formulas
Boolean Fourier Formulas
- Length
- 34 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Fourier expansion notation
Boolean Fourier formulas bridge the truth table of a boolean function and its multilinear polynomial representation. The lecture introduces the Walsh-Hadamard matrix to convert between function values and Fourier coefficients in linear time. It then proves the orthogonality of parity functions using expectation notation and the symmetric difference of subsets. Finally, it derives Parseval's formula, connecting the correlation of two boolean functions to the dot product of their Fourier coefficients.

Your comment is kept while you sign up.Sign in
O'Donnell proves parity functions orthogonal via symmetric differences of subsets, then derives Parseval's formula.
Boolean Fourier formulas bridge the truth table of a boolean function and its multilinear polynomial representation. The lecture introduces the Walsh-Hadamard matrix to convert between function values and Fourier coefficients in linear time. It then proves the orthogonality of parity functions using expectation notation and the symmetric difference of subsets. Finally, it derives Parseval's formula, connecting the correlation of two boolean functions to the dot product of their Fourier coefficients.
This lecture
Lecture 22 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.