# A Note on Hardness of Computing Recursive Teaching Dimension

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 39 references that are in the map.
- First posted on arXiv 19 Jul 2023.

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

- [Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique](https://mlsanity.com/paper/2211.01443/) (2022)
- [Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes](https://mlsanity.com/paper/1702.05677/) (2017)
- [Honest signaling in zero-sum games is hard, and lying is even harder](https://mlsanity.com/paper/1510.04991/) (2015)
- [Detecting communities is hard, and counting them is even harder](https://mlsanity.com/paper/1611.08326/) (2016)

## Abstract (arXiv)

In this short note, we show that the problem of computing the recursive teaching dimension (RTD) for a concept class (given explicitly as input) requires nOmega(log n)-time, assuming the exponential time hypothesis (ETH). This matches the running time nO(log n) of the brute-force algorithm for the problem.