Learning random monotone DNF
From MaRDI portal
Publication:628302
DOI10.1016/j.dam.2010.08.022zbMath1246.68133MaRDI QIDQ628302
Rocco A. Servedio, Jeffrey C. Jackson, Homin K. Lee, Andrew Wan
Publication date: 10 March 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.08.022
68Q32: Computational learning theory
68T05: Learning and adaptive systems in artificial intelligence
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On learning monotone DNF formulae under uniform distributions
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- On learning monotone DNF under product distributions
- On the learnability of disjunctive normal form formulas
- Learning monotone log-term DNF formulas under the uniform distribution
- The complexity of properly learning simple concept classes
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Constant depth circuits, Fourier transform, and learnability
- A theory of the learnable
- Computational limitations on learning from examples
- Learning Decision Trees Using the Fourier Spectrum
- Learning Boolean formulas
- On the Fourier spectrum of monotone functions
- On the noise sensitivity of monotone functions
- Exact learning of random DNF over the uniform distribution
- Learning Theory and Kernel Machines
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
