  Efficiently computing low discrepancy colorings of various set systems, has
been studied extensively since the breakthrough work by Bansal (FOCS 2010), who
gave the first polynomial time algorithms for several important settings,
including for general set systems, sparse set systems and for set systems with
bounded hereditary discrepancy. The hereditary discrepancy of a set system, is
the maximum discrepancy over all set systems obtainable by deleting a subset of
the ground elements. While being polynomial time, Bansal's algorithms were not
practical, with e.g. his algorithm for the hereditary setup running in time
$\Omega(m n^{4.5})$ for set systems with $m$ sets over a ground set of $n$
elements. More efficient algorithms have since then been developed for general
and sparse set systems, however, for the hereditary case, Bansal's algorithm
remains state-of-the-art. In this work, we give a significantly faster
algorithm with hereditary guarantees, running in $O(mn^2\lg(2 + m/n) + n^3)$
time. Our algorithm is based on new structural insights into set systems with
bounded hereditary discrepancy. We also implement our algorithm and show
experimentally that it computes colorings that are significantly better than
random and finishes in a reasonable amount of time, even on set systems with
thousands of sets over a ground set of thousands of elements.
