On Shallow Packings and Tusnadys Problem

Tusnadys problem asks to bound the discrepancy of points and axis-parallel boxes in $mathbb{R}^d$. Algorithmic bounds on Tusnadys problem use a canonical decomposition of Matouv{s}ek for the system of points and axis-parallel boxes, together with other techniques like partial coloring and / or random-walk based methods. We use the notion of emph{shallow cell complexity} and the emph{shallow packing lemma}, together with the chaining technique, to obtain an improved decomposition of the set system. Coupled with an algorithmic technique of Bansal and Garg for discrepancy minimization, which we also slightly extend, this yields improved algorithmic bounds on Tusnadys problem. For $dgeq 5$, our bound matches the lower bound of $Omega(log^{d-1}n)$ given by Matouv{s}ek, Nikolov and Talwar [IMRN, 2020] -- settling Tusnadys problem, upto constant factors. For $d=2,3,4$, we obtain improved algorithmic bounds of $O(log^{7/4}n)$, $O(log^{5/2}n)$ and $O(log^{13/4}n)$ respectively, which match or improve upon the non-constructive bounds of Nikolov for $dgeq 3$. Further, we also give improved bounds for the discrepancy of set systems of points and polytopes in $mathbb{R}^d$ generated via translations of a fixed set of hyperplanes. As an application, we also get a bound for the geometric discrepancy of anchored boxes in $mathbb{R}^d$ with respect to an arbitrary measure, matching the upper bound for the Lebesgue measure, which improves on a result of Aistleitner, Bilyk, and Nikolov [MC and QMC methods, emph{Springer, Proc. Math. Stat.}, 2018] for $dgeq 4$.