A note on hardness of computing recursive teaching dimension

DOI10.1016/J.IPL.2023.106429MaRDI QIDQ6072213zbMATH OpenOpenAlexFDO

Authors Pasin Manurangsi

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

zbMATH Keywords

computational complexityrecursive teaching dimensionfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32)

Recommendations

• Recursive teaching dimension, learning complexity, and maximum classes
• Sauer's bound for a notion of teaching complexity
• Recursive teaching dimension, VC-dimension and sample compression
• Combinatorial results on the complexity of teaching and learning
• Algebraic methods proving Sauer's bound for teaching complexity

Cites work

• Algebraic methods proving Sauer's bound for teaching complexity
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• Detecting communities is hard (and counting them is even harder)
• ETH hardness for densest-k-subgraph with perfect completeness
• Faster k-SAT algorithms using biased-PPSZ
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fundamentals of parameterized complexity
• Honest signaling in zero-sum games is hard, and lying is even harder
• Learning Binary Relations and Total Orders
• Lower bounds based on the exponential time hypothesis
• Models of cooperative teaching and learning
• On finding a minimum dominating set in a tournament
• On limited nondeterminism and the complexity of the V-C dimension
• On the Parameterized Complexity of Approximating Dominating Set
• On the complexity of k-SAT
• On the complexity of approximating the VC dimension.
• On the complexity of teaching
• On the possibility of faster \textsc{SAT} algorithms
• Optimal mistake bound learning is hard
• Population recovery and partial identification
• Recursive teaching dimension, VC-dimension and sample compression
• Reducibility among combinatorial problems
• Self-directed learning and its relation to the VC-dimension and to teacher-directed learning
• Teachability in computational learning
• Teaching and Compressing for Low VC-Dimension
• Which problems have strongly exponential complexity?

This page was built for publication: A note on hardness of computing recursive teaching dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072213)