Learning functions of k relevant variables

• DOI: 10.1016/j.jcss.2004.04.002
• Publication Date: 2004-06-07T11:55:43Z
• Authors: Elchanan Mossel; Ryan O'Donnell; Rocco A. Servedio
• Keywords: Computational Theory and Mathematics; Computer Networks and Communications; Applied Mathematics; PAC learning; 0202 electrical engineering, electronic engineering, information engineering; Computational learning theory; 02 engineering and technology; Boolean functions; Theoretical Computer Science

AbstractWe 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 (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.