hide
Free keywords:
Computer Science, Discrete Mathematics, cs.DM
Abstract:
We prove a size-sensitive version of Haussler's Packing
lemma~\cite{Haussler92spherepacking} for set-systems with bounded primal
shatter dimension, which have an additional {\em size-sensitive property}. This
answers a question asked by Ezra~\cite{Ezra-sizesendisc-soda-14}. We also
partially address another point raised by Ezra regarding overcounting of sets
in her chaining procedure. As a consequence of these improvements, we get an
improvement on the size-sensitive discrepancy bounds for set systems with the
above property. Improved bounds on the discrepancy for these special set
systems also imply an improvement in the sizes of {\em relative $(\varepsilon,
\delta)$-approximations} and $(\nu, \alpha)$-samples.
