Structural analysis of polynomial-time query learnability

DOI10.1007/BF01578844zbMath0809.68098OpenAlexW1980883546MaRDI QIDQ4298371

Ricard Gavaldà, Osamu Watanabe

Publication date: 20 March 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01578844

zbMATH Keywords

polynomial-time query learning systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (6)

Locating \(P\)/poly optimally in the extended low hierarchy ⋮ A framework for polynomial-time query learnability ⋮ On the complexity of small description and related topics ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Exact learning via teaching assistants ⋮ The complexity of learning concept classes with polynomial general dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Prediction-preserving reducibility
• The polynomial-time hierarchy
• When won't membership queries help?
• A theory of the learnable
• A framework for polynomial-time query learnability
• Cryptographic limitations on learning Boolean formulae and finite automata

This page was built for publication: Structural analysis of polynomial-time query learnability