Labeled Compression Schemes for Concept Classes of Finite Functions
arXiv:2603.235611.0h-index: 5
Predicted impact top 98% in IT · last 90 daysOriginality Incremental advance
AI Analysis
This solves a foundational problem in computational learning theory, with broad implications for machine learning and AI.
The paper resolves the long-standing sample compression conjecture by presenting a labeled compression scheme of size equal to the VC dimension for any concept class of finite functions.
The sample compression conjecture is: Each concept class of VC dimension d has a compression scheme of size d.In this paper, for any concept class of finite functions, we present a labeled sample compression scheme of size equals to its VC dimension d. That is, the long standing open sample compression conjecture is resolved.