O'Reilly logo

Analysis of Boolean Functions by Ryan O'Donnell

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required