Constant depth circuits, Fourier transform, and learnability

Abstract

Boolean functions in ACO are studied using the harmonic analysis of the cube. The main result is that an ACO Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in ACO: functions in ACO have low average sensitivity; they can be approximated well by a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wise independent probability distribution is small. An O(npolylog (n))-time algorithm for learning functions in ACO is obtained. The algorithm observes the behavior of an ACO function on O(npolylog (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.