License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.1
URN: urn:nbn:de:0030-drops-51091
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5109/
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 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.
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 = {1--15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-83-5},
ISSN = {1868-8969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5109},
URN = {urn:nbn:de:0030-drops-51091},
doi = {10.4230/LIPIcs.SOCG.2015.1},
annote = {Keywords: discrepancy theory, range counting, factorization norms}
}
|
Keywords: |
|
discrepancy theory, range counting, factorization norms |
|
Collection: |
|
31st International Symposium on Computational Geometry (SoCG 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
12.06.2015 |
