The complexity of learning concept classes with polynomial general dimension

DOI10.1016/j.tcs.2005.10.016zbMath1086.68064OpenAlexW2133696467MaRDI QIDQ817832

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

polynomial-time hierarchyquery learninglearning complexitylearning DNF formulas

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (2)

A general dimension for query learning ⋮ Characterizing Statistical Query Learning: Simplified Notions and Proofs

Cites Work

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

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