2014/08/06 by Matousek, Jiri, Nikolov, Aleksandar, Talwar, Kunal · 5 citations
#05B20 #05D05 #11K38 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1408.1376
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 E⊆ℝ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 Ω(logd-1 n) for the d-dimensional Tusnády 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.