Unlabeled Compression Schemes Exceeding the VC-dimension
Not on the map. Why?
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.
Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 Nov 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 2; 2023: 1; 2024: 0; 2025: 1.
6 papers.
- 2022Sample compression schemes for balls in graphscited by 9
- 2021Labeled sample compression schemes for complexes of oriented matroidscited by 7
- 2023Non-Clashing Teaching Maps for Balls in Graphscited by 6
- 2022Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classescited by 5
- 2025The Parameterized Complexity of Computing the VC-Dimensioncited by 2
- 2021Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversioncited by 0
- 2025The Parameterized Complexity of Computing the VC-Dimension20 Oct 2025
- 2023Non-Clashing Teaching Maps for Balls in Graphs6 Sep 2023
- 2022Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes11 Oct 2022
- 2022Sample compression schemes for balls in graphs27 Jun 2022
- 2021Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion29 Oct 2021
- 2021Labeled sample compression schemes for complexes of oriented matroids28 Oct 2021