Learnability Beyond AC^0.
J. Jackson and A. Klivans and R. Servedio.
34th Annual Symposium on Theory of Computing (STOC), 2002, pp. 776-784.
One-page abstract also appeared in Seventeenth Annual Conference on Computational Complexity (CCC), 2002, p. 26.

Abstract:

We give an algorithm to learn constant-depth polynomial-size circuits augmented with majority gates under the uniform distribution using random examples only. For circuits which contain a polylogarithmic number of majority gates the algorithm runs in quasipolynomial time. This is the first algorithm for learning a more expressive circuit class than the class $\AC^0$ of constant-depth polynomial-size circuits, a class which was shown to be learnable in quasipolynomial time by Linial, Mansour and Nisan in 1989. Our approach combines an extension of some of the Fourier analysis from Linial {\em et al.} with hypothesis boosting. We also show that under a standard cryptographic assumption our algorithm is essentially optimal with respect to both running time and expressiveness (number of majority gates) of the circuits being learned.