Teachability in computational learning
From MaRDI portal
DOI10.1007/BF03037091zbMATH Open0712.68084MaRDI QIDQ749233FDOQ749233
Authors: Ayumi Shinohara, Satoru Miyano 
Publication date: 1991
Published in: New Generation Computing (Search for Journal in Brave)
Recommendations
Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
Cited In (78)
- A note on hardness of computing recursive teaching dimension
- Sparse extractor families for all the entropy
- Sorting noisy data with partial information
- On the possibilities and limitations of pseudodeterministic algorithms
- Distinguishing pattern languages with membership examples
- Approximate testing and its relationship to learning
- Teaching and Compressing for Low VC-Dimension
- On the Teaching Complexity of Linear Sets
- The garden-hose model
- H-wise independence
- Differentially private data analysis of social networks via restricted sensitivity
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- On the power of nonuniformity in proofs of security
- Space-bounded communication complexity
- On the power of conditional samples in distribution testing
- Properties and applications of boolean function composition
- Teaching randomized learners with feedback
- Adversary lower bound for the k-sum problem
- Streaming computations with a loquacious prover
- On the learnability of recursively enumerable languages from good examples
- A theory of formal synthesis via inductive learning
- On Polynomial Time Constructions of Minimum Height Decision Tree
- Recent Developments in Algorithmic Teaching
- PAC learning under helpful distributions
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Decision lists and related Boolean functions
- A model of interactive teaching
- Queries revisited.
- New affine-invariant codes from lifting
- An energy complexity model for algorithms
- Exact learning from an honest teacher that answers membership queries
- Evasiveness through a circuit lens
- On the power of many one-bit provers
- Optimization problems for machine learning: a survey
- DNF are teachable in the average case
- Learning and incentives in user-generated content
- Reachability in graph timelines
- Combinatorial results on the complexity of teaching and learning
- Massive online teaching to bounded learners
- Algebraic methods proving Sauer's bound for teaching complexity
- Learnability of DNF with representation-specific queries
- Competing provers protocols for circuit evaluation
- On the convergence of the Hegselmann-Krause system
- Welfare maximization and the supermodular degree
- Characterizing the sample complexity of private learners
- Pseudo-partitions, transversality and locality
- Learning mixtures of spherical gaussians
- Stronger methods of making quantum interactive proofs perfectly complete
- Order compression schemes
- Catch them if you can
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Approaching utopia
- An equational approach to secure multi-party computation
- Can theories be tested?
- Low-weight halfspaces for sparse boolean vectors
- Making evolution rigorous
- Towards an optimal query efficient PCP?
- Robust optimization in the presence of uncertainty
- The teaching size: computable teachers and learners for universal languages
- Teacher-directed learning in view-independent face recognition with mixture of experts using single-view eigenspaces
- The complexity of exact learning of acyclic conditional preference networks from swap examples
- Finitely distinguishable erasing pattern languages
- The power of random counterexamples
- Runtime guarantees for regression problems
- Measuring teachability using variants of the teaching dimension
- Barriers in cryptography with weak, correlated and leaky sources
- Is privacy compatible with truthfulness?
- On the complexity of teaching
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
- Resource-based corruptions and the combinatorics of hidden diversity
- Classifying the Arithmetical Complexity of Teaching Models
- Publicly verifiable proofs of sequential work
- On the teaching complexity of linear sets
- On the limits of efficient teachability
- Time hierarchies for sampling distributions
- Exact learning via teaching assistants
- A characterization of approximation resistance for even k-partite CSPs
- On specifying Boolean functions by labelled examples
This page was built for publication: Teachability in computational learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q749233)
