Prediction-preserving reducibility
From MaRDI portal
Publication:756441
DOI10.1016/0022-0000(90)90028-JzbMath0722.68094OpenAlexW2020114845WikidataQ56017510 ScholiaQ56017510MaRDI QIDQ756441
Manfred K. Warmuth, Leonard Pitt
Publication date: 1990
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(90)90028-j
computational learning theoryprediction-preserving reducibilityprobably approximately correct learning algorithm
Learning and adaptive systems in artificial intelligence (68T05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Learning elementary formal systems with queries., Prefix grammars: An alternative characterization of the regular languages, The query complexity of learning DFA, The learnability of description logics with equality constraints, Learning fallible deterministic finite automata, Minimizing nfa's and regular expressions, Efficient learning of typical finite automata from random walks, A framework for polynomial-time query learnability, Structural analysis of polynomial-time query learnability, Logical settings for concept-learning, Learning unions of tree patterns using queries, Learning orthogonal F-Horn formulas, The complexity of learning minor closed graph classes, On the intrinsic complexity of learning recursive functions, On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes, Learnability of quantified formulas., Equivalence of models for polynomial learnability, Classic learning, On the necessity of Occam algorithms, Learning unions of tree patterns using queries, Learning orthogonal F-Horn formulas, Three \(\sum^ P_ 2\)-complete problems in computational learning theory, Random Embedding Machines for Pattern Recognition, Partial observability and learnability, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions, Pac-learning non-recursive Prolog clauses, Pac-learning non-recursive Prolog clauses, Learning commutative deterministic finite state automata in polynomial time, Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes, Unnamed Item, Learning with unreliable boundary queries, Approximating hyper-rectangles: Learning and pseudorandom sets, Interactive Clustering of Linear Classes and Cryptographic Lower Bounds, On-line learning of linear functions, On learning unions of pattern languages and tree patterns in the mistake bound model., Apple tasting., Prediction-hardness of acyclic conjunctive queries
Cites Work
- \(\epsilon\)-nets and simplex range queries
- Learning regular sets from queries and counterexamples
- One way functions and pseudorandom generators
- Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
- Occam's razor
- \(\varepsilon\)-productions in context-free grammars
- On uniform circuit complexity
- Analogical and inductive inference. International workshop AII '89, Reinhardsbrunn Castle, GDR, October 1-6, 1989. Proceedings
- On the necessity of Occam algorithms
- On tape-bounded complexity classes and multihead finite automata
- Space-bounded reducibility among combinatorial problems
- Complete problems for deterministic polynomial time
- Linear programming is log-space hard for P
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Learning decision trees from random examples
- A general lower bound on the number of examples needed for learning
- Density and dimension
- Queries and concept learning
- Learnability and the Vapnik-Chervonenkis dimension
- A taxonomy of problems with fast parallel algorithms
- A theory of the learnable
- Computational limitations on learning from examples
- Alternation
- The minimum consistent DFA problem cannot be approximated within any polynomial
- Computational Complexity of Probabilistic Turing Machines
- Complexity of automaton identification from given data
- On the Tape Complexity of Deterministic Context-Free Languages
- On the complexity of minimum inference of regular sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
