On PAC learning algorithms for rich Boolean function classes.
L. Hellerstein and R. Servedio.
Theoretical Computer Science 384 (1), 2007, pp. 66--76.
Preliminary version appeared in 3rd Annual Conference on Theory and Applications of Models of Computation (TAMC), 2006, pp. 442--451. (Invited paper.)


We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube $\{0,1\}^n$ and sparse $GF_2$ polynomials over $\{0,1\}^n.$

pdf of conference version

Postscript or pdf (full version).

Back to main papers page