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.


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.

Postscript or pdf.

Back to main papers page