https://www.youtube.com/watch?v=JIruJ8edYYM&index=1&list=PLm3J0oaFux3YypJNaF6sRAf2zC1QzMuTA

Fourier decomposition of Boolean functions (Harmonic analysis of Boolean functions) – decomposition as a Multilinear polynomial (aka multilinear expansion), which always exists and is unique.

Parseval's theorem, Plancherel theorem

Convolution theorem also generalizes, etc.

Linearity testing

Learning Boolean functions

See Probably approximately correct and Learning theory

See this video for how to learn Boolean functions which have their Fourier coefficients concentrated in some terms. (definition of epsilon-concentration, for the special case where the set of terms where it's concentrated is those with degree less than $k$)

Similar result to Occam algorithms (learning functions with spectrum concentrated at low degree).

Proposition: A Boolean function is $\epsilon$ concentrated up to degree total influence of f / $\epsilon$ – Every monotone functions is concentrated on degree up to O(sqrt(n))

Goldreich-Levin theorem

Finding the set of terms with large Fourier coefficients using Goldreich-Levin theorem, which allows to learn Boolean functions which are spectrally concentrated, efficiently, given query access

Can also learn small decision trees efficiently (Boolean functions computed by low-depth Decision trees have concentrated spectra!, by writting the multilinear expansion using path-indicators)