2010-11-30 Learning using the Fourier spectrum

Today we presented the basics of Fourier analysis of boolean functions, and showed an algorithm that learns functions with (epsilon,d)-degree (= whose Fourier coefficients for parities of more than d variables have low squared sum).

This technique (as well as the application to constant-depth circuits that
we will see next day) is from:
- Constant-depth circuits, Fourier transform and learnability, N. Linial Y. Mansour and N. Nisan, Jour. Assoc. Comput. Mach., 40 (1993) 607 - 620.

The exposition in this and next lecture largely follows:

- Learning Boolean Functions via the Fourier Transform, by Y. Mansour (1994).

Exercise 21: Prove Parseval's identity with the hint given in class.

Exercise 22: Prove that the Fourier transform of the Fourier transform of f is f.

Exercise 23: Prove Claim 1 in the proof of correctness of the (epsilon,d)-degree learning algorithm.