Learning DNF from Random Walks.
N. Bshouty and E. Mossel and R. O'Donnell and R. Servedio.
Journal of Computer and System Sciences 71(3), 2005, pp. 250-265 (special issue for STOC, FOCS, and COLT 2003).
Preliminary version in 44th Annual Symposium on Foundations of Computer Science (FOCS), 2003, pp. 189-198.


We consider a model of learning Boolean functions from examples generated by a uniform random walk on $\{0,1\}^n$. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.

Postscript or pdf of conference version

pdf of journal version

Back to main papers page