VC Dimension

VC: Vapnik-Chervonenkis

Latest papers

9 papers3 papers in the last four weeks, level with the four weeks before. 0.0% of all new 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
Optimal VC Dimension of Contrastive Learning with Margin
Sep 30, 2026Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1Contrastive Learning Geometric Representation Learning
Northwestern University · UC Santa Cruz
VC Dimension and Expressivity of Real-Valued Transformers
Sep 25, 2026Gavin Dooley, Andy Yang, Yijia Jessica Zhu +3VC Dimension Transformer Expressivity
University of Notre Dame
Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
Sep 19, 2026Martin AnthonyVC Dimension Prototype-Based Classification
Department of Mathematics London School of Economics and Political Science, London, UK
Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails
Sep 3, 2026Shi Fu, Huibo Xu, Qixin Zhang +1Sparse Recovery Heavy-Tailed Noise
Generative AI Lab, College of Computing and Data Science, Nanyang Technological University, Singapore
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
The VC dimension of partial concept classes via Radon's theorem
Jul 12, 2026Grigory Ivanov, Attila Jung, Márton NaszódiVC Dimension
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
Uniform Laws of Large Numbers in Product Spaces
Mar 25, 2026Ron Holzman, Shay Moran, Alexander ShlimovichVC Dimension Statistical Learning Theory
Department of Mathematics, Technion · Departments of Mathematics, Computer Science, and Data and Decision Sciences, Technion and Google Research

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.