On the complexity of teaching
From MaRDI portal
Publication:1892202
DOI10.1006/jcss.1995.1003zbMath0939.68770OpenAlexW2020764470MaRDI QIDQ1892202
Sally A. Goldman, Michael Kearns
Publication date: 5 July 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1995.1003
Related Items
Online learning of binary and \(n\)-ary relations over clustered domains. ⋮ Exact learning from an honest teacher that answers membership queries ⋮ On specifying Boolean functions by labelled examples ⋮ LARS: a learning algorithm for rewriting systems ⋮ A general dimension for query learning ⋮ A model of interactive teaching ⋮ Distinguishing pattern languages with membership examples ⋮ Approximate testing and its relationship to learning ⋮ From undecidability of non-triviality and finiteness to undecidability of learnability ⋮ A note on hardness of computing recursive teaching dimension ⋮ Learning Tree Languages ⋮ 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 ⋮ Unnamed Item ⋮ PAC Learning under Helpful Distributions ⋮ Teaching randomized learners with feedback ⋮ Unnamed Item ⋮ 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 ⋮ Beneficial and harmful explanatory machine learning ⋮ When are epsilon-nets small? ⋮ On Polynomial Time Constructions of Minimum Height Decision Tree ⋮ On Version Space Compression ⋮ Classifying the Arithmetical Complexity of Teaching Models ⋮ On the Teaching Complexity of Linear Sets ⋮ The teaching size: computable teachers and learners for universal languages ⋮ Exact learning via teaching assistants ⋮ The subsumption lattice and query learning ⋮ On Boolean threshold functions with minimum specification number ⋮ On the limits of efficient teachability ⋮ A new abstract combinatorial dimension for exact learning via queries ⋮ Uniform characterizations of polynomial-query learnabilities
