- Series
- Combinatorics Seminar
- Time
- Tuesday, October 21, 2014 - 1:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Esther Ezra – NYU Polytechnic School of Engineering
- Organizer
- Prasad Tetali
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.