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