Complexity theoretic hardness results for query learning

DOI10.1007/PL00001593MaRDI QIDQ1266164zbMATH OpenOpenAlexFDO

Authors Tibor Hegedűs, Lisa Hellerstein, Leonard Pitt, Howard Aizenstein

Publication date 26 October 1998

Published in Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

learning algorithmrepresentation problem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• scientific article; zbMATH DE number 1256690
• scientific article; zbMATH DE number 1263194
• How many queries are needed to learn?
• Exact learning of DNF formulas using DNF hypotheses
• On the limits of proper learnability of subclasses of DNF formulas

Cited in

(33)

• Conjunctions of unate DNF formulas: Learning and structure
• Hardness results for learning first-order representations and programming by demonstration
• General lower bounds on the query complexity within the exact learning model
• When won't membership queries help?
• Oracles and queries that are sufficient for exact learning
• New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
• Learning read-constant polynomials of constant degree modulo composites
• On the hardness of learning queries from tree structured data
• The complexity of properly learning simple concept classes
• Exact learning from an honest teacher that answers membership queries
• Simulating access to hidden information while learning
• On the Nonlearnability of a Single Spiking Neuron
• scientific article; zbMATH DE number 1256690 (Why is no real title available?)
• scientific article; zbMATH DE number 1263194 (Why is no real title available?)
• Structural analysis of polynomial-time query learnability
• scientific article; zbMATH DE number 1966613 (Why is no real title available?)
• scientific article; zbMATH DE number 1563912 (Why is no real title available?)
• On the Power of Learning from k-Wise Queries
• From average case complexity to improper learning complexity
• Algorithmic Learning Theory
• Algorithmic Learning Theory
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• Exact learning algorithms, betting games, and circuit lower bounds
• Exact learning of DNF formulas using DNF hypotheses
• Decision lists and related Boolean functions
• Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
• On the structure of learnability beyond P/poly
• Learning concepts definable in first-order logic with counting
• The parameterized complexity of learning monadic second-order logic
• Learning aggregate queries defined by first-order logic with counting
• Version spaces and the consistency problem
• Theory revision with queries: Horn, read-once, and parity formulas
• The complexity of learning concept classes with polynomial general dimension

This page was built for publication: Complexity theoretic hardness results for query learning

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