Constant depth circuits, Fourier transform, and learnability

Boolean functions in AC^O are studied using the harmonic analysis of the cube. The main result is that an AC^O Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in AC^O: functions in AC^O have low average sensitivity; they can be approximated well be a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wide independent probability distribution is small. An O(n^{polylog{ sup} (n)})-time algorithm for learning functions in AC^O is obtained. The algorithm observed the behavior of an AC^O function on O(n^{polylog (n)}) randomly chosen inputs and derives a good approximation for the Fourier transform of the function. This allows it to predict with high probability the value of the function on other randomly chosen inputs