The No-Clash Teaching Dimension is Bounded by VC Dimension

Jiahua Liu; Benchong Li

cs.ITMar 24, 2026

The No-Clash Teaching Dimension is Bounded by VC Dimension

Authors: Jiahua Liu, Benchong Li

Organizations: School of Mathematics and Statistics, Xidian University.

Abstract

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.

Sample Compression

See all 8 papers

On Collusion-Free Teaching in Planar Graphs
Oct 13, 2026Khazaliya Liana, Kuske ClemensVC Dimension Statistical Learning Theory
Aalto University, Espoo, Finland · Helsinki Institute for Information Technology, Helsinki, Finland · Hasso Plattner Institute, Potsdam, Germany
A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
Aug 31, 2026Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira RodriguesPAC Learning Statistical Learning Theory
Contradiction Graphs Determine VC Dimension
May 19, 2026Jesse Campbell, Daniel Ibaibarriaga, Lev ReyzinStatistical Learning Theory VC Dimension
Department of Mathematics, Statistics, & Computer Science University of Illinois Chicago

Oct 13, 2026J/K move · Enter open · S save

On Collusion-Free Teaching in Planar Graphs

Khazaliya Liana, Kuske Clemens

Aalto University, Espoo, Finland · Helsinki Institute for Information Technology, Helsinki, Finland · Hasso Plattner Institute, Potsdam, Germany

VC Dimension Statistical Learning Theory

Open paper AskPDF arXiv

Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.

Abstract

Sample Compression

Explore similar work

On Collusion-Free Teaching in Planar Graphs

A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

Contradiction Graphs Determine VC Dimension