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.
One way a Boolean function’s Fourier spectrum can be “simple” is for it to be mostly concentrated at small degree.
Definition 3.1. We say that the Fourier spectrum of is -concentrated on degree up to if