The Parameterized Complexity of Computing the VC-Dimension

Jun-12-2026, 10:20:57 GMT–Neural Information Processing Systems

The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension.

artificial intelligence, machine learning, proceedings, (9 more...)

Neural Information Processing Systems

Jun-12-2026, 10:20:57 GMT

Conferences Web Page

Add feedback

Technology:
- Information Technology > Artificial Intelligence > Machine Learning (1.00)