mlsanityData to 13 Oct 2026

A Note on Hardness of Computing Recursive Teaching Dimension

arXiv 2307.09792 ↗First posted 19 Jul 2023cs.CC cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

4 of 39 references.

References · 4

  1. 2022Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Bicliquecited by 7
  2. 2017Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classescited by 6
  3. 2015Honest signaling in zero-sum games is hard, and lying is even hardercited by 1
  4. 2016Detecting communities is hard, and counting them is even hardercited by 1

Built on by

Not cited yet.