Exact learning of DNF formulas using DNF hypotheses

DOI10.1145/509907.509976MaRDI QIDQ5901048zbMATH OpenOpenAlexFDO

Authors Lisa Hellerstein, Vijay Raghavan

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/509907.509976

Mathematics Subject Classification ID

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

Cited in

(5)

• The complexity of properly learning simple concept classes
• Polynomial certificates for propositional classes
• Exact learning of DNF formulas using DNF hypotheses
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• The DNF exception problem

This page was built for publication: Exact learning of DNF formulas using DNF hypotheses

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