§3.4: Learning theory

Computational learning theory is an area of algorithms research devoted to the following task: given a source of “examples” $(x, f(x))$ from an unknown function $f$, compute a “hypothesis” function $h$ which is good at predicting $f(y)$ on future inputs $y$. We will focus on just one possible formulation of the task:

[...]

§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.

[...]