Learning using group representations (extended abstract)
Dan Boneh · 1995
We consider the problem of learning functions over a fixed distribution.An algorithm by Kushilevitz and Mansour [7] learns boolean functions over {O, I}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.