Structural analysis of polynomial-time query learnability
From MaRDI portal
Recommendations
- A framework for polynomial-time query learnability
- Uniform characterizations of polynomial-query learnabilities
- Complexity theoretic hardness results for query learning
- Learnability of solutions to conjunctive queries
- Polynomial Time Probabilistic Learning of a Subclass of Linear Languages with Queries
- On the hardness of learning queries from tree structured data
- New Computational Paradigms
- General lower bounds on the query complexity within the exact learning model
- Learning via finitely many queries
- On the structure of learnability beyond P/poly
Cites work
- A framework for polynomial-time query learnability
- A theory of the learnable
- Cryptographic limitations on learning Boolean formulae and finite automata
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 177810 (Why is no real title available?)
- Prediction-preserving reducibility
- The polynomial-time hierarchy
- When won't membership queries help?
Cited in
(9)- Locating P/poly optimally in the extended low hierarchy
- Exact learning via teaching assistants
- Cryptographic limitations on polynomial-time posteriori query learning
- On the hardness of learning queries from tree structured data
- Efficient learning algorithms yield circuit lower bounds
- scientific article; zbMATH DE number 177810 (Why is no real title available?)
- A framework for polynomial-time query learnability
- On the complexity of small description and related topics
- The complexity of learning concept classes with polynomial general dimension
This page was built for publication: Structural analysis of polynomial-time query learnability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4298371)
