# Labeled sample compression schemes for complexes of oriented matroids

arXiv: https://arxiv.org/abs/2110.15168 · HTML: https://mlsanity.com/paper/2110.15168/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 81 references that are in the map.
- First posted on arXiv 28 Oct 2021.

## Builds on (most cited first, 12 of 12)

- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [On transversality of bent hyperplane arrangements and the topological expressiveness of ReLU neural networks](https://mlsanity.com/paper/2008.09052/) (2020)
- [Unlabeled sample compression schemes and corner peelings for ample and maximum classes](https://mlsanity.com/paper/1812.02099/) (2018)
- [Labeled compression schemes for extremal classes](https://mlsanity.com/paper/1506.00165/) (2015)
- [Unlabeled Compression Schemes Exceeding the VC-dimension](https://mlsanity.com/paper/1811.12471/) (2018)
- [Bounding Embeddings of VC Classes into Maximum Classes](https://mlsanity.com/paper/1401.7388/) (2014)
- [Hyperplane Neural Codes and the Polar Complex](https://mlsanity.com/paper/1801.02304/) (2018)
- [Sweeps, polytopes, oriented matroids, and allowable graphs of permutations](https://mlsanity.com/paper/2102.06134/) (2021)

## Built on by (most cited first, 7 of 7)

- [Sample compression schemes for balls in graphs](https://mlsanity.com/paper/2206.13254/) (2022)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Dual VC Dimension Obstructs Sample Compression by Embeddings](https://mlsanity.com/paper/2405.17120/) (2024)
- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)

## Abstract (arXiv)

We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension d admit a proper labeled sample compression scheme of size d. This considerably extends results of Moran and Warmuth on ample classes, of Ben-David and Litman on affine arrangements of hyperplanes, and of the authors on complexes of uniform oriented matroids, and is a step towards the sample compression conjecture -- one of the oldest open problems in computational learning theory. On the one hand, our approach exploits the rich combinatorial cell structure of COMs via oriented matroid theory. On the other hand, viewing tope graphs of COMs as partial cubes creates a fruitful link to metric graph theory.