A subexponential exact learning algorithm for DNF using equivalence queries
From MaRDI portal
Publication:1847366
DOI10.1016/0020-0190(96)00077-4zbMATH Open1046.68635OpenAlexW2020712580MaRDI QIDQ1847366FDOQ1847366
Publication date: 24 June 2003
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(96)00077-4
Recommendations
- scientific article; zbMATH DE number 2077165
- Exact learning of DNF formulas using DNF hypotheses
- On the limits of proper learnability of subclasses of DNF formulas
- Learnability of DNF with representation-specific queries
- Fast learning of \(k\)-term DNF formulas with queries.
- On Exact Learning Monotone DNF from Membership Queries
- New bounds for the query complexity of an algorithm that learns DFAs with correction and equivalence queries
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Proper learning of \(k\)-term DNF formulas from satisfying assignments
Cites Work
Cited In (10)
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Title not available (Why is that?)
- Hardness Characterisations and Size-width Lower Bounds for QBF Resolution
- Solving linear constraints over real and rational fields
- On PAC learning algorithms for rich Boolean function classes
- The complexity of properly learning simple concept classes
- Learning Theory
- Learning Pseudo-Boolean k-DNF and Submodular Functions
- On the limits of proper learnability of subclasses of DNF formulas
- Exact learning of DNF formulas using DNF hypotheses
This page was built for publication: A subexponential exact learning algorithm for DNF using equivalence queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1847366)
