Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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 ? in time O((nk/?)k+1) under any product distribution on {0, 1}n using read-once branching programs as a hypothesis. This gives the first poly(n, 1/?) algorithm for learning even the intersection of 2 halfspaces under the uniform distribution on {0, 1}n previously known algorithms had an exponential dependence either on the accuracy parameter ? 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.

Questions and Answers

You need to be logged in to be able to post here.