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 (n k ) ω/(ω + 1) , where ω < 2.376 is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive n k time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.

Authors

• Elchanan Mossel
• Ryan O'Donnell
• Rocco A. Servedio

Keywords

• fourier
• juntas
• learning
• relevant variables
• uniform distribution