Learning using group representations
Authors: D. Boneh
Abstract:
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.
Reference:
In Proceedings COLT 1995, pp. 418--426, Santa Cruz, California
Full paper: gzipped-PostScript [first posted 11/1995 ]