Learning random monotone DNF
- 1 March 2011
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 159 (5) , 259-271
Abstract
No abstract availableKeywords
Funding Information
- NSF (CCF-02090641, CCF-0728939)
- NSF (CCF-0347282, CCF-0523664)
- NSF
- Sloan Foundation Fellowship
This publication has 26 references indexed in Scilit:
- Hardness of approximate two-level logic minimization and PAC learning with membership queriesJournal of Computer and System Sciences, 2009
- The complexity of properly learning simple concept classesJournal of Computer and System Sciences, 2008
- On learning monotone DNF under product distributionsInformation and Computation, 2004
- On the noise sensitivity of monotone functionsRandom Structures & Algorithms, 2003
- On the Fourier spectrum of monotone functionsJournal of the ACM, 1996
- On the learnability of disjunctive normal form formulasMachine Learning, 1995
- Learning Boolean formulasJournal of the ACM, 1994
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993
- Computational limitations on learning from examplesJournal of the ACM, 1988
- A theory of the learnableCommunications of the ACM, 1984