Unlabeled compression schemes exceeding the VC-dimension

Palvolgyi, D; Tardos, G

Palvolgyi, D (corresponding author), Eotvos Lorand Univ, Inst Math, MTA ELTE Lendulet Combinatorial Geometry Res Grp, Budapest, Hungary.

DISCRETE APPLIED MATHEMATICS, 2020; 276 (): 102

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......

Full Text Link