Labeled Compression Schemes for Concept Classes of Finite Functions

arXiv:2603.23561v1 Announce Type: new
Abstract: 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.