@inproceedings{gopalan2012learning,
author = {Gopalan, Parikshit and Klivans, Adam and Meka, Raghu},
title = {Learning functions of halfspaces using prefix covers},
booktitle = {COLT'12},
year = {2012},
month = {June},
abstract = {We present a simple query-algorithm for learning arbitrary functions of k halfspaces under any product distribution on the Boolean hypercube. Our algorithms learn any function of k halfspaces to within accuracy eps in time O((nk/eps)k+1) under any product distribution on 0,1n using read-once branching programs as a hypothesis.. This gives the fifirst poly(n, 1/eps) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on 0,1n; previously known algorithms had an exponential dependence either on the accuracy parameter eps or the dimension n. To prove this result, we identify a new structural property of Boolean functions that yields learnability with queries: that of having a small prefix cover.},
publisher = {Journal of Machine Learning Research},
url = {http://approjects.co.za/?big=en-us/research/publication/learning-functions-of-halfspaces-using-prefix-covers/},
edition = {COLT'12},
}