The complexity of learning concept classes with polynomial general dimension

DOI10.1016/J.TCS.2005.10.016zbMATH Open1086.68064OpenAlexW2133696467MaRDI QIDQ817832FDOQ817832

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

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

zbMATH Keywords

query learninglearning complexitypolynomial-time hierarchylearning DNF formulas

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Characterizing statistical query learning: simplified notions and proofs
• 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)