Oracles and queries that are sufficient for exact learning
From MaRDI portal
Publication:1924380
DOI10.1006/jcss.1996.0032zbMath0858.68075OpenAlexW2069652878MaRDI 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
Related Items (38)
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ Attribute-efficient learning of Boolean functions from Post closed classes ⋮ Learning nearly monotone \(k\)-term DNF ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ A model of interactive teaching ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Average-case intractability vs. worst-case intractability ⋮ On the Limit of Some Algorithmic Approach to Circuit Lower Bounds ⋮ The power of natural properties as oracles ⋮ Learning from examples with unspecified attribute values. ⋮ Learning Grammars and Automata with Queries ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Arthur and Merlin as oracles ⋮ Two queries ⋮ The unbiased black-box complexity of partition is polynomial ⋮ Unnamed Item ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ Quantum algorithms for learning and testing juntas ⋮ New collapse consequences of NP having small circuits ⋮ Proving SAT does not have small circuits with an application to the two queries problem ⋮ The 1-versus-2 queries problem revisited ⋮ Learning expressions and programs over monoids ⋮ Improved bounds on quantum learning algorithms ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Unnamed Item ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Parameterized learnability of juntas ⋮ The learnability of exclusive-or expansions based on monotone DNF formulas ⋮ Exact learning via teaching assistants ⋮ Quantum learning of concentrated Boolean functions ⋮ Randomness vs time: Derandomization under a uniform assumption ⋮ A new abstract combinatorial dimension for exact learning via queries ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound ⋮ Uniform characterizations of polynomial-query learnabilities ⋮ The complexity of learning concept classes with polynomial general dimension
This page was built for publication: Oracles and queries that are sufficient for exact learning
