A Note on Hardness of Computing Recursive Teaching Dimension

Pasin Manurangsi
7/19/2023
cs.CCcs.LG

No confident code implementation found for this paper.

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{manurangsi2023note,
  title  = {A Note on Hardness of Computing Recursive Teaching Dimension},
  author = {Pasin Manurangsi},
  year   = {2023},
  eprint = {2307.09792},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2307.09792v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2307.09792.svg)](https://codeofpaper.com/paper/2307.09792)

Discussion