Oracles and queries that are sufficient for exact learning
From MaRDI portal
Publication:1924380
DOI10.1006/jcss.1996.0032zbMath0858.68075MaRDI QIDQ1924380
Sampath Kannan, Christino Tamon, Nader H. Bshouty, Richard Cleve, Ricard Gavaldà
Publication date: 26 November 1996
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1880/45748
68T05: Learning and adaptive systems in artificial intelligence
Related Items
New collapse consequences of NP having small circuits, Unnamed Item, Unnamed Item, On Pseudodeterministic Approximation Algorithms., The 1-Versus-2 Queries Problem Revisited, The power of natural properties as oracles, Learning nearly monotone \(k\)-term DNF, The unbiased black-box complexity of partition is polynomial, Average-case intractability vs. worst-case intractability, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Arthur and Merlin as oracles, The complexity of learning concept classes with polynomial general dimension, Attribute-efficient learning of Boolean functions from Post closed classes, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), The 1-versus-2 queries problem revisited, Parameterized learnability of juntas, A model of interactive teaching, Learning from examples with unspecified attribute values., The learnability of exclusive-or expansions based on monotone DNF formulas, Exact learning via teaching assistants, Randomness vs time: Derandomization under a uniform assumption, A new abstract combinatorial dimension for exact learning via queries, Competing provers yield improved Karp-Lipton collapse results, Uniform characterizations of polynomial-query learnabilities, New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., Two queries, Quantum learning of concentrated Boolean functions, Quantum algorithms for learning symmetric juntas via the adversary bound, Quantum algorithms for learning and testing juntas, Proving SAT does not have small circuits with an application to the two queries problem, Learning expressions and programs over monoids, Improved bounds on quantum learning algorithms, Exact learning from an honest teacher that answers membership queries, Circuit lower bounds from learning-theoretic approaches, $$P\mathop{ =}\limits^{?}NP$$, On the Limit of Some Algorithmic Approach to Circuit Lower Bounds, Learning Grammars and Automata with Queries, Parameterized Learnability of k-Juntas and Related Problems
