# The No-Clash Teaching Dimension is Bounded by VC Dimension

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 8 references that are in the map.
- First posted on arXiv 24 Mar 2026.

## Builds on (most cited first, 1 of 1)

- [Optimal Collusion-Free Teaching](https://mlsanity.com/paper/1903.04012/) (2019)

## Abstract (arXiv)

In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching. However, whether No-Clash Teaching Dimension is upper-bounded by Vapnik-Chervonenkis dimension remains unknown. In this paper, for any finite concept class, we construct fragments of size equals to its Vapnik-Chervonenkis dimension which identify concepts through an ordered compression scheme. Naturally, these fragments are used as teaching sets, one can easily see that they satisfy the non-clashing condition, i.e., this open question is resolved for finite concept classes.