CONSTANT DEPTH CIRCUITS, FOURIER-TRANSFORM, AND LEARNABILITY

In this paper, Boolean functions in AC0 are studied using harmonic analysis on the cube. The main result is that an AC0 Boolean function has almost all of its ''power spectrum'' on the low-order coefficients. An important ingredient of the proof is Hastad's switching lemma [8]. This result implies several new properties of functions in AC0: Functions in AC0 have low ''average sensitivity;'' they may be approximated well by a real polynomial of low degree and they cannot be pseudorandom function generators. Perhaps the most interesting application is an O(n(polylog(n)))-time algorithm for learning functions in AC0. The algorithm observes the behavior of an AC0 function on O(n(polylog(n))) randomly chosen inputs, and derives a good approximation for the Fourier transform of the function. This approximation allows the algorithm to predict, with high probability, the value of the function on other randomly chosen inputs.