Kolja Knauer: Sample Compression Schemes for Complexes of Oriented Matroids
Time: Wed 2022-03-23 10.15 - 11.15
Location: Zoom meeting ID: 654 5562 3260
Abstract: Complexes of Oriented Matroids (COMs) are a common generalization of Oriented Matroids and Ample Set Systems. I will motivate them through the combinatorics of polytopes sliced by hyperplanes and introduce some of their theory.
Based on this I will present a sample compression scheme of size d for COMs of VC-dimension d. This extends ideas and results of Moran and Warmuth for Ample Set Systems and establishes the largest class for which the sample compression conjecture is known to hold - a long-standing open problem in computational learning theory.
I will try to gently introduce all participating objects and see some nice connections between computational geometry, metric graph theory, and computational learning theory.
Joint work with Victor Chepoi and Manon Philibert.
Zoom meeting ID: 654 5562 3260
Zoom link: https://kth-se.zoom.us/j/65455623260