Shallow Packings: Revisiting Haussler's Proof

Esther Ezra, NYU Polytechnic School of Engineering

September 16, 2014

In this talk I will present the notion of a $\delta$-packing for set systems of bounded primal shatter dimension (closely related to the notion of finite VC-dimension). The structure of $\delta$-packing, which has been studied by Dudley in 1978 and Haussler in 1995, emerges from empirical processes and is fundamental in theoretical computer science and in computational geometry in particular. Moreover, it has applications in geometric discrepancy, range searching, and epsilon-approximations, to name a few.

I will discuss a variant of $\delta$-packings where all the sets have small cardinality, we call these structures "shallow packings", and then present an upper bound on their size under additional natural assumptions on the set system, which correspond to several geometric settings, among which is the case of points and halfspaces in d-dimensions.