One reasonable way to assess the “complexity” of a boolean function is in terms how complex its Fourier spectrum is. For example, functions with sufficiently simple Fourier spectra can be efficiently *learned* from examples. This chapter will be concerned with understanding the location, magnitude, and structure of a boolean function’s Fourier spectrum.

## Leave a Reply