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