Paper Info
Title
Unlabeled compression schemes exceeding the VC-dimension
Abstract
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.
Year
DOI
Venue
2020
10.1016/j.dam.2019.09.022
Discrete Applied Mathematics
Keywords
DocType
Volume
Learning theory,Compression schemes,VC-dimension
Journal
276
Issue
ISSN
Citations 
C
0166-218X
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
Dömötör Pálvölgyi120229.14
Gábor Tardos21261140.58