Prediction-preserving reducibility
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3889430 (Why is no real title available?)
- scientific article; zbMATH DE number 3878983 (Why is no real title available?)
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 67615 (Why is no real title available?)
- scientific article; zbMATH DE number 67633 (Why is no real title available?)
- scientific article; zbMATH DE number 3566175 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3420728 (Why is no real title available?)
- A general lower bound on the number of examples needed for learning
- A taxonomy of problems with fast parallel algorithms
- A theory of the learnable
- Alternation
- Analogical and inductive inference. International workshop AII '89, Reinhardsbrunn Castle, GDR, October 1-6, 1989. Proceedings
- Complete problems for deterministic polynomial time
- Complexity of automaton identification from given data
- Computational Complexity of Probabilistic Turing Machines
- Computational limitations on learning from examples
- Density and dimension
- Learnability and the Vapnik-Chervonenkis dimension
- Learning decision trees from random examples
- Learning regular sets from queries and counterexamples
- Linear programming is log-space hard for P
- Occam's razor
- On tape-bounded complexity classes and multihead finite automata
- On the Tape Complexity of Deterministic Context-Free Languages
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the complexity of minimum inference of regular sets
- On the necessity of Occam algorithms
- On uniform circuit complexity
- One way functions and pseudorandom generators
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
- Queries and concept learning
- Space-bounded reducibility among combinatorial problems
- The minimum consistent DFA problem cannot be approximated within any polynomial
- \(\epsilon\)-nets and simplex range queries
- \(\varepsilon\)-productions in context-free grammars
Cited in
(39)- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- On-line learning of linear functions
- Prediction-hardness of acyclic conjunctive queries
- Structural analysis of polynomial-time query learnability
- On the intrinsic complexity of learning recursive functions
- Classic learning
- Prefix grammars: An alternative characterization of the regular languages
- Random embedding machines for pattern recognition
- The query complexity of learning DFA
- Efficient learning of typical finite automata from random walks
- A framework for polynomial-time query learnability
- Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
- On the necessity of Occam algorithms
- Learning commutative deterministic finite state automata in polynomial time
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- On reduction of two-parameter prediction problems
- Learning with unreliable boundary queries
- Learnability of quantified formulas.
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Learning fallible deterministic finite automata
- Interactive clustering of linear classes and cryptographic lower bounds
- Pac-learning non-recursive Prolog clauses
- Partial observability and learnability
- Learning unions of tree patterns using queries
- Learning orthogonal F-Horn formulas
- Learning elementary formal systems with queries.
- Apple tasting.
- Learning unions of tree patterns using queries
- Learnability of solutions to conjunctive queries
- The learnability of description logics with equality constraints
- Equivalence of models for polynomial learnability
- Logical settings for concept-learning
- Pac-learning non-recursive Prolog clauses
- Learning orthogonal F-Horn formulas
- scientific article; zbMATH DE number 1839442 (Why is no real title available?)
- The complexity of learning minor closed graph classes
- On learning unions of pattern languages and tree patterns in the mistake bound model.
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Minimizing nfa's and regular expressions
This page was built for publication: Prediction-preserving reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q756441)
