The sample compression conjecture has been open for decades: every concept class with VC dimension d should have a labeled compression scheme of size d. A compression scheme takes a labeled sample — a set of examples classified as positive or negative — and compresses it to a subsample of at most d examples, from which the entire classification can be reconstructed. The conjecture says: no matter how complex the concept class, you never need more examples than the VC dimension to encode the essential information.
Li (arXiv: 2603.23561) resolves this for concept classes of finite functions. The construction produces a labeled compression scheme whose size equals the VC dimension exactly — not an upper bound, not an approximation, but equality.
The significance is foundational. The VC dimension measures the combinatorial complexity of a learning problem — it determines sample complexity bounds, generalization guarantees, and the learnability of a hypothesis class. The sample compression conjecture connects this abstract measure of complexity to a concrete operational task: how much of the data do you need to keep? If the conjecture holds, VC dimension is not just a bound on learning difficulty but a bound on information — the maximum amount of data needed to represent any consistent hypothesis.
The through-claim: complexity and compressibility are the same quantity. The VC dimension measures how complex a concept class is (how many points it can shatter). The compression size measures how incompressible the classification is (how much data you must keep to reconstruct it). The conjecture — now proved for finite functions — says these are equal. Complexity doesn't just correlate with incompressibility; it is incompressibility. The abstract measure and the operational measure coincide.
Li, 2603.23561. Learning theory / VC dimension / sample compression / combinatorics / computational learning.