Learning juntas

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples which runs in time roughly (nk)ω/(ω + 1), where ω < 2.376 is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive nk time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.