The complexity of learning concept classes with polynomial general dimension

DOI10.1016/J.TCS.2005.10.016MaRDI QIDQ817832zbMATH OpenOpenAlexFDO

Authors Johannes Köbler, Wolfgang Lindner

Publication date 20 March 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.10.016

zbMATH Keywords

query learninglearning complexitypolynomial-time hierarchylearning DNF formulas

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• scientific article; zbMATH DE number 1966613
• A general dimension for query learning
• scientific article; zbMATH DE number 1263194
• How many queries are needed to learn?
• Oracles and queries that are sufficient for exact learning

Cites work

• scientific article; zbMATH DE number 1804113 (Why is no real title available?)
• scientific article; zbMATH DE number 67616 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1563912 (Why is no real title available?)
• A framework for polynomial-time query learnability
• A new abstract combinatorial dimension for exact learning via queries
• Complexity theoretic hardness results for query learning
• Cryptographic limitations on learning Boolean formulae and finite automata
• How many queries are needed to learn?
• Learning read-once formulas with queries
• Oracles and queries that are sufficient for exact learning
• Queries and concept learning
• Structural analysis of polynomial-time query learnability
• When won't membership queries help?

Cited in

(3)

• Characterizing statistical query learning: simplified notions and proofs
• scientific article; zbMATH DE number 1966613 (Why is no real title available?)
• A general dimension for query learning

This page was built for publication: The complexity of learning concept classes with polynomial general dimension

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