Learning random monotone DNF

DOI10.1016/J.DAM.2010.08.022zbMATH Open1246.68133OpenAlexW3021060265MaRDI QIDQ628302FDOQ628302

Jeffrey 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

Recommendations

• Learning Random Monotone DNF
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On learning random DNF formulas under the uniform distribution
• scientific article; zbMATH DE number 1804125
• Exact learning of random DNF over the uniform distribution

zbMATH Keywords

Fourier analysiscomputational learning theorymonotone Boolean function

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32)

Cites Work

• Learning Decision Trees Using the Fourier Spectrum
• Constant depth circuits, Fourier transform, and learnability
• A theory of the learnable
• Title not available (Why is that?)
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Computational limitations on learning from examples
• Learning Boolean formulas
• Title not available (Why is that?)
• On the Fourier spectrum of monotone functions
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• On the noise sensitivity of monotone functions
• The complexity of properly learning simple concept classes
• Exact learning of random DNF over the uniform distribution
• Learning monotone log-term DNF formulas under the uniform distribution
• Title not available (Why is that?)
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• On learning monotone DNF formulae under uniform distributions
• On learning monotone DNF under product distributions
• On the learnability of disjunctive normal form formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Learning random log-depth decision trees under the uniform distribution.

Cited In (6)

• Learning Random Monotone DNF
• Exact learning from an honest teacher that answers membership queries
• Learning Monotone Decision Trees in Polynomial Time
• On using the Fourier transform to learn disjoint DNF
• On learning monotone DNF formulae under uniform distributions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Learning random monotone DNF

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q628302)