Tusnády's problem in $d$ dimensions asks for the smallest possible value $\Delta_d(n)$ for which any $n$-point set $P$ in $\mathbb{R}^d$ can be two-colored so that no axis-aligned box has more than $\Delta_d(n)$ points of one color in excess of the other. In 1981, Beck showed that $\Delta_d(n)$ is bounded from below by the Lebesgue-measure discrepancy of axis-aligned boxes, which is known to be at least $\Omega(\log^{(d-1)/2} n)$. On the other hand, the best known upper bound for $\Delta_d(n)$ is considerably larger: Larsen gave a bound of $O(\log^{d + 1/2} n)$, slightly improving on a previous result of Matoušek. We nearly close this gap and show a new lower bound of $\Omega(\log^{d-1} n)$. We also give a new simple proof of the upper bound. Our results are proved via the ellipsoid-infinity norm, defined for a matrix $A$ as the the minimum $\ell_\infty$ norm of a $0$-centered ellipsoid $E$ that contains all column vectors of $A$. The ellipsoid-infinity norm approximates hereditary discrepancy up to logarithmic factors and satisfies a number of nice properties, such as the triangle inequality and multiplicativity with respect to Kronecker products, making it a powerful tool in combinatorial discrepancy theory.
Joint work with Jiří Matoušek.