Fourier Analysis and Boolean Function Learning

Jeff Jackson

Fourier analysis has informed a number of positive and negative results

regarding the learnability of Boolean functions. In turn, learning

research has led to the discovery of Fourier properties of various

Boolean function classes. I will survey Fourier properties and

associated learning results for several interesting Boolean classes,

including monotone functions, disjunctive normal form (DNF) expressions,

constant-depth circuits more generally, and halfspaces. Some flavor of

the underlying Fourier analysis will be included.