Opening Fourier Analysis of Boolean Functions
Fourier Analysis of Boolean Functions
- Length
- 32 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Before the lecture
Fourier analysis of Boolean functions writes any real-valued function on the -dimensional hypercube as a multilinear polynomial. O'Donnell sets up the formalism in both and notation, showing why the real-number encoding turns xor into multiplication. Working through majority of three and parity, he builds interpolating polynomials vertex by vertex from indicator polynomials. The construction yields the theorem that every function from -bit strings to the reals has a unique multilinear representation. Reading that polynomial as a combination of parity monomials gives the Fourier expansion, whose coefficients encode combinatorial properties of the function. Part of Carnegie Mellon's graduate course A Theorist's Toolkit, the session assumes basic linear algebra and probability and follows O'Donnell's book Analysis of Boolean Functions.
Your comment is kept while you sign up.Sign in
Interpolates majority-of-three vertex by vertex on the cube to show every Boolean function is a multilinear polynomial.
Fourier analysis of Boolean functions writes any real-valued function on the -dimensional hypercube as a multilinear polynomial. O'Donnell sets up the formalism in both and notation, showing why the real-number encoding turns xor into multiplication. Working through majority of three and parity, he builds interpolating polynomials vertex by vertex from indicator polynomials. The construction yields the theorem that every function from -bit strings to the reals has a unique multilinear representation. Reading that polynomial as a combination of parity monomials gives the Fourier expansion, whose coefficients encode combinatorial properties of the function. Part of Carnegie Mellon's graduate course A Theorist's Toolkit, the session assumes basic linear algebra and probability and follows O'Donnell's book Analysis of Boolean Functions.
This lecture
Lecture 21 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.