Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-129 | 25th October 2007 00:00

Learning Random Monotone DNF

RSS-Feed

Abstract:

We give an algorithm that with high probability properly learns random monotone t(n)-term
DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF hypothesis. This is the first algorithm that can learn monotone DNF of arbitrary polynomial size in a reasonable average-case model of learning from random examples only.



ISSN 1433-8092 | Imprint