A Geometric Approach to Sample Compression
  The Sample Compression Conjecture of Littlestone & Warmuth has remained
unsolved for over two decades. This paper presents a systematic geometric
investigation of the compression of finite maximum concept classes. Simple
arrangements of hyperplanes in Hyperbolic space, and Piecewise-Linear
hyperplane arrangements, are shown to represent maximum classes, generalizing
the corresponding Euclidean result. A main result is that PL arrangements can
be swept by a moving hyperplane to unlabeled d-compress any finite maximum
class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary
is that some d-maximal classes cannot be embedded into any maximum class of VC
dimension d+k, for any constant k. The construction of the PL sweeping involves
Pachner moves on the one-inclusion graph, corresponding to moves of a
hyperplane across the intersection of d other hyperplanes. This extends the
well known Pachner moves for triangulations to cubical complexes.
