Matoušek, Jirí ;
Nikolov, Aleksandar
Combinatorial Discrepancy for Boxes via the gamma_2 Norm
Abstract
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 0centered ellipsoid E that in turn is contained in the hypercube [t, t]^m. This classical quantity is polynomialtime 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)^(d1) (up to constant factors) for the ddimensional Tusnady problem, asking for the combinatorial discrepancy of an npoint set in ddimensional space with respect to axisparallel boxes. For d>2, this improves the previous best lower bound, which was of order approximately log(n)^((d1)/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.
BibTeX  Entry
@InProceedings{matouek_et_al:LIPIcs:2015:5109,
author = {Jir{\'i} Matou{\v{s}}ek and Aleksandar Nikolov},
title = {{Combinatorial Discrepancy for Boxes via the gamma_2 Norm}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {115},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5109},
URN = {urn:nbn:de:0030drops51091},
doi = {10.4230/LIPIcs.SOCG.2015.1},
annote = {Keywords: discrepancy theory, range counting, factorization norms}
}
2015
Keywords: 

discrepancy theory, range counting, factorization norms 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

2015 