Learning using group representations

Authors: D. Boneh

We consider the problem of learning functions over a fixed distribution. An algorithm by Kushilevitz and Mansour learns boolean functions over {0,1}^n in time polynomial in the L1 norm of the Fourier transform of the function. We show that the KM-algorithm is a special case of a more general class of learning algorithms. This is achieved by extending their ideas using representations of finite groups. We introduce some new classes of functions which can be learned using this generalized KM algorithm.

In Proceedings COLT 1995, pp. 418--426, Santa Cruz, California

Full paper: gzipped-PostScript         [first posted 11/1995 ]