(2022) Sample Compression Schemes for Balls in Graphs.
In: MFCS 2022.
Conference:
MFCS International Symposium on Mathematical Foundations of Computer Science
|
Text
LIPIcs-MFCS-2022-31.pdf - Published Version Download (931kB) | Preview |
Abstract
One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Conference: | MFCS International Symposium on Mathematical Foundations of Computer Science |
| Depositing User: | Fionn Mc Inerney |
| Date Deposited: | 23 Sep 2022 07:07 |
| Last Modified: | 23 Sep 2022 07:07 |
| Primary Research Area: | NRA2: Reliable Security Guarantees |
| URI: | https://publications.cispa.saarland/id/eprint/3783 |
Actions
Actions (login required)
 |
View Item |