The asymptotic unlabeled compression conjecture for powers of
The asymptotic unlabeled compression conjecture for powers of
Let be the family defined earlier in the source, let denote its -fold join, and let be the minimum size of an unlabeled compression scheme for . The asymptotic conjecture.
exists and is strictly larger than . The question concerns the asymptotic gap between VC-dimension and unlabeled compression size for joins; the source does not establish either the existence of the limit or the strict inequality.
Sources & referencesView supporting material
Primary source
Dömötör Pálvölgyi and Gábor Tardos, “Unlabeled Compression Schemes Exceeding the VC-dimension”, arXiv:1811.12471 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.