# Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2017.

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

- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension](https://mlsanity.com/paper/2212.12631/) (2022)
- [A Note on Hardness of Computing Recursive Teaching Dimension](https://mlsanity.com/paper/2307.09792/) (2023)
- [Lower Bounds for Greedy Teaching Set Constructions](https://mlsanity.com/paper/2505.03223/) (2025)
- [Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization](https://mlsanity.com/paper/2605.22964/) (2026)

## Abstract (arXiv)

In this work we study the quantitative relation between the recursive teaching dimension (RTD) and the VC dimension (VCD) of concept classes of finite sizes. The RTD of a concept class mathcal C subseteq 0, 1n, introduced by Zilles et al. (2011), is a combinatorial complexity measure characterized by the worst-case number of examples necessary to identify a concept in mathcal C according to the recursive teaching model. For any finite concept class mathcal C subseteq 0,1n with VCD(mathcal C)=d, Simon & Zilles (2015) posed an open problem RTD(mathcal C) = O(d), i.e., is RTD linearly upper bounded by VCD? Previously, the best known result is an exponential upper bound RTD(mathcal C) = O(d · 2d), due to Chen et al. (2016). In this paper, we show a quadratic upper bound: RTD(mathcal C) = O(d2), much closer to an answer to the open problem. We also discuss the challenges in fully solving the problem.