# Unlabeled Compression Schemes Exceeding the VC-dimension

arXiv: https://arxiv.org/abs/1811.12471 · HTML: https://mlsanity.com/paper/1811.12471/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2018.

## Built on by (most cited first, 6 of 6)

- [Sample compression schemes for balls in graphs](https://mlsanity.com/paper/2206.13254/) (2022)
- [Labeled sample compression schemes for complexes of oriented matroids](https://mlsanity.com/paper/2110.15168/) (2021)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes](https://mlsanity.com/paper/2210.05455/) (2022)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion](https://mlsanity.com/paper/2111.00062/) (2021)

## Abstract (arXiv)

In this note we disprove a conjecture of Kuzmin and Warmuth claiming that every family whose VC-dimension is at most d admits an unlabeled compression scheme to a sample of size at most d. We also study the unlabeled compression schemes of the joins of some families and conjecture that these give a larger gap between the VC-dimension and the size of the smallest unlabeled compression scheme for them.