A Note on Hardness of Computing Recursive Teaching Dimension
Pasin Manurangsi
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 $n^{\Omega(\log n)}$-time, assuming the exponential time hypothesis
(ETH). This matches the running time $n^{O(\log n)}$ of the brute-force
algorithm for the problem.