1 Search Results for "Matoušek, Jirí"

Document

DOI: 10.4230/LIPIcs.SOCG.2015.1

Combinatorial Discrepancy for Boxes via the gamma_2 Norm

Authors: Jirí Matoušek and Aleksandar Nikolov

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

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.

Cite as

Jirí Matoušek and Aleksandar Nikolov. Combinatorial Discrepancy for Boxes via the gamma_2 Norm. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{matousek_et_al:LIPIcs.SOCG.2015.1,
  author =	{Matou\v{s}ek, Jir{\'\i} and Nikolov, Aleksandar},
  title =	{{Combinatorial Discrepancy for Boxes via the gamma\underline2 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 =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.1},
  URN =		{urn:nbn:de:0030-drops-51091},
  doi =		{10.4230/LIPIcs.SOCG.2015.1},
  annote =	{Keywords: discrepancy theory, range counting, factorization norms}
}

Refine by Author
1 Matoušek, Jirí
1 Nikolov, Aleksandar

Refine by Classification

Refine by Keyword
1 discrepancy theory
1 factorization norms
1 range counting

Refine by Type
1 document

Refine by Publication Year
1 2015

1 Search Results for "Matoušek, Jirí"

Combinatorial Discrepancy for Boxes via the gamma_2 Norm

Abstract

Cite as

Thanks for your feedback!

Could not send message