A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

Esther Ezra

Let $(X,\S )$ be a set system on an $n$-point set $X$. The \emph{discrepancy} of $\S$ is defined as the minimum of the largest deviation from an even split, over all subsets of $S \in…