Labeled sample compression schemes for complexes of oriented matroids
  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.
