# Optimal Collusion-Free Teaching

arXiv: https://arxiv.org/abs/1903.04012 · HTML: https://mlsanity.com/paper/1903.04012/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2019.

## Built on by (most cited first, 8 of 8)

- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [MAP- and MLE-Based Teaching](https://mlsanity.com/paper/2307.05252/) (2023)
- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)
- [A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension](https://mlsanity.com/paper/2212.12631/) (2022)
- [The No-Clash Teaching Dimension is Bounded by VC Dimension](https://mlsanity.com/paper/2603.23561/) (2026)
- [On Collusion-Free Teaching in Planar Graphs](https://mlsanity.com/paper/2610.18714/) (2026)

## Abstract (arXiv)

Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-freeness was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model M and each concept class C, a parameter M-TD(C) refers to the teaching dimension of concept class C in model M---defined to be the number of examples required for teaching a concept, in the worst case over all concepts in C. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter NCTD(C). No-clash teaching is provably optimal in the strong sense that, given any concept class C and any model M obeying Goldman and Mathias's collusion-freeness criterion, one obtains NCTD(C)≤ M-TD(C). We also study a corresponding notion NCTD^+ for the case of learning from positive data only, establish useful bounds on NCTD and NCTD^+, and discuss relations of these parameters to the VC-dimension and to sample compression. In addition to formulating an optimal model of collusion-free teaching, our main results are on the computational complexity of deciding whether NCTD^+(C)=k (or NCTD(C)=k) for given C and k. We show some such decision problems to be equivalent to the existence question for certain constrained matchings in bipartite graphs. Our NP-hardness results for the latter are of independent interest in the study of constrained graph matchings.