2026-08-17T06:27:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5109 2024-03-06T10:35:49Z ddc:004 open_access

Combinatorial Discrepancy for Boxes via the gamma_2 Norm Matoušek, Jirí Nikolov, Aleksandar discrepancy theory range counting factorization norms The gamma_2 norm of a real m by n matrix A is the minimum number t such that the column vectors of A are contained in a 0-centered ellipsoid E that in turn is contained in the hypercube [-t, t]^m. This classical quantity is polynomial-time computable and was proved by the second author and Talwar to approximate the hereditary discrepancy: it bounds the hereditary discrepancy from above and from below, up to logarithmic factors. Here we provided a simplified proof of the upper bound and show that both the upper and the lower bound are asymptotically tight in the worst case. 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 log(n)^(d-1) (up to constant factors) for the d-dimensional Tusnady problem, asking for the combinatorial discrepancy of an n-point set in d-dimensional space with respect to axis-parallel boxes. For d>2, this improves the previous best lower bound, which was of order approximately log(n)^((d-1)/2), and it comes close to the best known upper bound of O(log(n)^(d+1/2)), for which we also obtain a new, very simple proof. Applications to lower bounds for dynamic range searching and lower bounds in differential privacy are given. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jirí Matoušek and Aleksandar Nikolov 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.1 urn:nbn:de:0030-drops-51091 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.1 eng https://creativecommons.org/licenses/by/3.0/legalcode