ECCC-Report TR07-129https://eccc.weizmann.ac.il/report/2007/129Comments and Revisions published for TR07-129en-usSat, 08 Dec 2007 23:03:20 +0200
Paper TR07-129
| Learning Random Monotone DNF |
Jeffrey C. Jackson,
Homin Lee,
Rocco Servedio,
Andrew Wan
https://eccc.weizmann.ac.il/report/2007/129We 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.
Sat, 08 Dec 2007 23:03:20 +0200https://eccc.weizmann.ac.il/report/2007/129