A note on hardness of computing recursive teaching dimension
From MaRDI portal
Publication:6072213
DOI10.1016/j.ipl.2023.106429zbMath1529.68126arXiv2307.09792OpenAlexW4385076082MaRDI QIDQ6072213
Publication date: 12 October 2023
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2307.09792
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Population recovery and partial identification
- Fundamentals of parameterized complexity
- Algebraic methods proving Sauer's bound for teaching complexity
- Teachability in computational learning
- On finding a minimum dominating set in a tournament
- Optimal mistake bound learning is hard
- Self-directed learning and its relation to the VC-dimension and to teacher-directed learning
- Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
- Which problems have strongly exponential complexity?
- On limited nondeterminism and the complexity of the V-C dimension
- On the complexity of approximating the VC dimension.
- On the complexity of teaching
- Learning Binary Relations and Total Orders
- ETH Hardness for Densest-k-Subgraph with Perfect Completeness
- Teaching and Compressing for Low VC-Dimension
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Reducibility among Combinatorial Problems
- Honest signaling in zero-sum games is hard, and lying is even harder
- Faster k -SAT algorithms using biased-PPSZ
- On the Parameterized Complexity of Approximating Dominating Set
- Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
- On the complexity of \(k\)-SAT
This page was built for publication: A note on hardness of computing recursive teaching dimension
