# 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 ]