查看文章

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function that depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples that 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.