# 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.