Factorization Norms and Hereditary Discrepancy

The γ2 norm of a real m× n matrix A is the minimum number t such that the column vectors of A are contained in a 0-centered ellipsoid Esubseteqℝ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: γ2(A) = O(log m)· herdisc A and herdisc A = O(√log m,)·γ2(A) . Since γ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 γ2 norm as a tool for proving lower and upper bounds in discrepancy theory. Most notably, we prove a new lower bound of Omega(logd-1 n) for the d-dimensional Tusn'ady problem, asking for the combinatorial discrepancy of an n-point set in ℝ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)/2n, and it comes close to the best known upper bound of O(logd+1/2n), for which we also obtain a new, very simple proof.