Unlabeled Compression Schemes Exceeding the VC-dimension

November 29, 2018 · The Ethereal · 🏛 Discrete Applied Mathematics

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Dömötör Pálvölgyi, Gábor Tardos arXiv ID 1811.12471 Category math.CO: Combinatorics Cross-listed cs.DM, cs.LG Citations 10 Venue Discrete Applied Mathematics Last Checked 2 months ago
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Combinatorics

🔮 🔮 The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO 🏛 arXiv 📚 94 cites 10 years ago