Size sensitive packing number for Hamming cube and its consequences
This work addresses theoretical problems in computational geometry and discrepancy theory, with incremental improvements to existing bounds.
The authors proved a size-sensitive version of Haussler's Packing lemma for set-systems with bounded primal shatter dimension and a size-sensitive property, answering a question by Ezra, and improved discrepancy bounds, leading to better sizes for relative approximations and samples.
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, δ)$-approximations} and $(ν, α)$-samples.