Factorization Norms and Hereditary Discrepancy

The |$\gamma _{2}$| norm of a real m × n matrix A is the minimumnumber t such that the column vectors of A are contained in a 0-centered ellipsoid |$E\subseteq{\mathbb{R}}^{m}$| which in turn is contained in the hypercube |$[-t, t]^{m}$|⁠. We prove that this classical quantity approximates the hereditary discrepancy herdisc A as follows: |$\gamma _{2}(A) ={O(\log m)}\cdot \operatorname{herdisc} A$| and |$\operatorname{herdisc}\, A = O\big (\sqrt{\log m}\,\big )\cdot \gamma _{2}(A) $|⁠. Since |$\gamma _{2}$| is polynomial-time computable, this gives a polynomial-time approximation algorithm for hereditary discrepancy. Both inequalities are shown to be asymptotically tight. We then demonstrate on several examples the power of the |$\gamma _{2}$| norm as a tool for proving lower and upper bounds in discrepancy theory. Most notably, we prove a new lower bound of |$\varOmega\!\! \left (\log ^{d-1} n \right )$| for the d-dimensional Tusnády problem, asking for the combinatorial discrepancy of an n-point set in |${\mathbb{R}}^{d}$| with respect to axis-parallel boxes. For d > 2, this improves the previous best lower bound, which was of order approximately |$\log ^{(d-1)/2}n$|⁠.