CONSTANT DEPTH CIRCUITS, FOURIER-TRANSFORM, AND LEARNABILITY

In this paper, Boolean functions in AC0 are studied using harmonic ana lysis on the cube. The main result is that an AC0 Boolean function has almost all of its ''power spectrum'' on the low-order coefficients. A n important ingredient of the proof is Hastad's switching lemma [8]. T his result implies several new properties of functions in AC0: Functio ns in AC0 have low ''average sensitivity;'' they may be approximated w ell 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 algo rithm observes the behavior of an AC0 function on O(n(polylog(n))) ran domly 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 ran domly chosen inputs.