## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Chapter 3 Spectral Structure and Learning

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.

### 3.1. Low-Degree Spectral Concentration

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

For ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required