Nabil Mustafa (ESIEE Paris): Sampling in Geometric Set Systems, and Applications: Recent Progress

This course will present the ideas and techniques behind constructing samples for a variety of geometric configurations. We will then present some recent algorithmic applications to geometric optimization problems. The course will start with combinatorics of geometric set systems (e.g., VC-dimension, shallow-cell complexity), leading to packing analogues for combinatorial set systems. These combinatorial bounds will then be used to construct small-sized samples of geometric configurations (e.g., epsilon-nets, epsilon-approximations, relative approximations). Finally, we will see how this can be used to construct coresets for optimization problems (e.g., k-means, projective clustering) using the technique of Feldman-Langberg-Schulman.