A Note on Hardness of Computing Recursive Teaching Dimension
This work addresses a theoretical problem in computational learning theory, providing a tight hardness result for RTD computation, which is incremental as it confirms the optimality of existing methods.
The authors tackled the computational complexity of computing the recursive teaching dimension (RTD) for concept classes, showing that it requires n^{Ω(log n)} time under the exponential time hypothesis, matching the brute-force algorithm's runtime.
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^{Ω(\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.