Prediction-preserving reducibility
From MaRDI portal
Publication:756441
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
- -nets and simplex range queries
- -productions in context-free grammars
Cited in
(39)- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- Learning fallible deterministic finite automata
- Learning orthogonal F-Horn formulas
- Learnability of quantified formulas.
- Equivalence of models for polynomial learnability
- Learning orthogonal F-Horn formulas
- Partial observability and learnability
- The learnability of description logics with equality constraints
- Prediction-hardness of acyclic conjunctive queries
- A framework for polynomial-time query learnability
- Classic learning
- Learning unions of tree patterns using queries
- The complexity of learning minor closed graph classes
- Learning unions of tree patterns using queries
- Random embedding machines for pattern recognition
- Logical settings for concept-learning
- On reduction of two-parameter prediction problems
- On the intrinsic complexity of learning recursive functions
- Interactive clustering of linear classes and cryptographic lower bounds
- Apple tasting.
- On-line learning of linear functions
- Learning commutative deterministic finite state automata in polynomial time
- On learning unions of pattern languages and tree patterns in the mistake bound model.
- Learning with unreliable boundary queries
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Pac-learning non-recursive Prolog clauses
- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- Prefix grammars: An alternative characterization of the regular languages
- The query complexity of learning DFA
- On the necessity of Occam algorithms
- Structural analysis of polynomial-time query learnability
- Minimizing nfa's and regular expressions
- scientific article; zbMATH DE number 1839442 (Why is no real title available?)
- Learnability of solutions to conjunctive queries
- Learning elementary formal systems with queries.
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
- Efficient learning of typical finite automata from random walks
- Pac-learning non-recursive Prolog clauses
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)
