A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
Let $(X,\EuScript{S})$ be a set system on an $n$-point set $X$. The discrepancy of $\EuScript{S}$ is defined as the minimum of the largest deviation from an even split, over all subsets of $S \in \EuScript{S}$ and two-colorings $\chi$ on $X$. We consider the scenario where, for any subset $X' \subseteq …