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
- Evasiveness through a circuit lens (extended abstract)
- 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
- Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
- Teaching randomized learners with feedback
- 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
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Decision lists and related Boolean functions
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Approaching utopia, strong truthfulness and externality-resistant mechanisms
- A model of interactive teaching
- Queries revisited.
- New affine-invariant codes from lifting
- Making evolution rigorous: the error threshold
- An energy complexity model for algorithms
- Exact learning from an honest teacher that answers membership queries
- On the power of many one-bit provers
- Optimization problems for machine learning: a survey
- DNF are teachable in the average case
- 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
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
- On the convergence of the Hegselmann-Krause system
- Welfare maximization and the supermodular degree
- Characterizing the sample complexity of private learners
- Stronger methods of making quantum interactive proofs perfectly complete
- Classifying the arithmetical complexity of teaching models
- Order compression schemes
- Catch them if you can
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- An equational approach to secure multi-party computation
- A characterization of approximation resistance for even \(k\)-partite CSPs
- Can theories be tested?
- Low-weight halfspaces for sparse boolean vectors
- 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
- Resource-based corruptions and the combinatorics of hidden diversity
- Publicly verifiable proofs of sequential work
- On the teaching complexity of linear sets
- On the limits of efficient teachability
- \(H\)-wise independence
- Properties and applications of Boolean function composition
- Time hierarchies for sampling distributions
- Exact learning via teaching assistants
- Adversary lower bound for the \(k\)-sum problem
- 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)
