Learning random monotone DNF

DOI10.1016/j.dam.2010.08.022zbMath1246.68133MaRDI QIDQ628302

Jeffrey C. Jackson, Andrew Wan, Homin K. Lee, Rocco A. Servedio

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

zbMATH Keywords

computational learning theory; Fourier analysis; monotone Boolean function

Mathematics Subject Classification ID

68Q32: Computational learning theory

68T05: Learning and adaptive systems in artificial intelligence

Related Items

Exact learning from an honest teacher that answers membership queries

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