A Note on Hardness of Computing Recursive Teaching Dimension

2023/07/19 by Manurangsi, Pasin
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2307.09792

Abstract

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.

Related

• Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes
• Lower Bounds for Greedy Teaching Set Constructions
• RTD-Conjecture and Concept Classes Induced by Graphs
• Preference-based Teaching
• Classifying the Arithmetical Complexity of Teaching Models