Document Open Access Logo

Combinatorial Discrepancy for Boxes via the gamma_2 Norm

Authors Jirí Matoušek, Aleksandar Nikolov

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.1.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Jirí Matoušek
Aleksandar Nikolov

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.SOCG.2015.1

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.

Subject Classification

Keywords
  • discrepancy theory
  • range counting
  • factorization norms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. T. van Aardenne-Ehrenfest. Proof of the impossibility of a just distribution of an infinite sequence of points. Nederl. Akad. Wet., Proc., 48:266-271, 1945. Also in Indag. Math. 7, 71-76 (1945). Google Scholar
  2. T. van Aardenne-Ehrenfest. On the impossibility of a just distribution. Nederl. Akad. Wet., Proc., 52:734-739, 1949. Also in Indag. Math. 11, 264-269 (1949). Google Scholar
  3. J. R. Alexander, J. Beck, and W. W. L. Chen. Geometric discrepancy theory and uniform distribution. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 10, pages 185-207. CRC Press LLC, Boca Raton, FL, 1997. Google Scholar
  4. N. Bansal. Constructive algorithms for discrepancy minimization. http://arxiv.org/abs/1002.2259, also in FOCS'10: Proc. 51st IEEE Symposium on Foundations of Computer Science, pages 3-10, 2010.
  5. J. Beck. Balanced two-colorings of finite sets in the square. I. Combinatorica, 1:327-335, 1981. Google Scholar
  6. J. Beck. Balanced two-colorings of finite sets in the cube. Discrete Mathematics, 73:13-25, 1989. Google Scholar
  7. J. Beck. A two-dimensional van Aardenne-Ehrenfest theorem in irregularities of distribution. Compositio Math., 72:269-339, 1989. Google Scholar
  8. J. Beck and W. W. L. Chen. Irregularities of Distribution. Cambridge University Press, Cambridge, 1987. Google Scholar
  9. Rajendra Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997. Google Scholar
  10. D. Bilyk and M. T. Lacey. On the small ball inequality in three dimensions. Duke Math. J., 143(1):81-115, 2008. Google Scholar
  11. D. Bilyk, M. T. Lacey, and A. Vagharshakyan. On the small ball inequality in all dimensions. J. Funct. Anal., 254(9):2470-2502, 2008. Google Scholar
  12. G. Bohus. On the discrepancy of 3 permutations. Random Struct. Algo., 1:215-220, 1990. Google Scholar
  13. J. Bourgain and L. Tzafriri. Invertibility of large submatrices with applications to the geometry of banach spaces and harmonic analysis. Israel journal of mathematics, 57(2):137-224, 1987. Google Scholar
  14. M. Charikar, A. Newman, and A. Nikolov. Tight hardness results for minimizing discrepancy. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California, USA, pages 1607-1614, 2011. Google Scholar
  15. B. Chazelle. The Discrepancy Method. Cambridge University Press, Cambridge, 2000. Google Scholar
  16. B. Chazelle and A. Lvov. A trace bound for the hereditary discrepancy. Discrete Comput. Geom., 26(2):221-231, 2001. Google Scholar
  17. B. Chazelle and A. Lvov. The discrepancy of boxes in higher dimension. Discrete Comput. Geom., 25(4):519-524, 2001. Google Scholar
  18. J. G. van der Corput. Verteilungsfunktionen I. Akad. Wetensch. Amsterdam, Proc., 38:813-821, 1935. Google Scholar
  19. J. G. van der Corput. Verteilungsfunktionen II. Akad. Wetensch. Amsterdam, Proc., 38:1058-1066, 1935. Google Scholar
  20. M. Drmota and R. F. Tichy. Sequences, discrepancies and applications (Lecture Notes in Mathematics 1651). Springer-Verlag, Berlin etc., 1997. Google Scholar
  21. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014. Google Scholar
  22. Michael L. Fredman. The complexity of maintaining an array and computing its partial sums. J. ACM, 29(1):250-260, 1982. Google Scholar
  23. J. H. Halton. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math., 2:84-90, 1960. Google Scholar
  24. J. M. Hammersley. Monte Carlo methods for solving multivariable problems. Ann. New York Acad. Sci., 86:844-874, 1960. Google Scholar
  25. K. G. Larsen. On range searching in the group model and combinatorial discrepancy. SIAM Journal on Computing, 43(2):673-686, 2014. Google Scholar
  26. Troy Lee, Adi Shraibman, and Robert Špalek. A direct product theorem for discrepancy. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pages 71-80. IEEE Computer Society, 2008. Google Scholar
  27. Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. Complexity measures of sign matrices. Combinatorica, 27(4):439-463, 2007. Google Scholar
  28. L. Lovász, J. Spencer, and K. Vesztergombi. Discrepancy of set-systems and matrices. European J. Combin., 7:151-160, 1986. Google Scholar
  29. J. Matoušek. The determinant bound for discrepancy is almost tight. Proc. Amer. Math. Soc., 141(2):451-460, 2013. Google Scholar
  30. J. Matoušek. On the discrepancy for boxes and polytopes. Monatsh. Math., 127(4):325-336, 1999. Google Scholar
  31. J. Matoušek. Geometric Discrepancy (An Illustrated Guide), 2nd printing. Springer-Verlag, Berlin, 2010. Google Scholar
  32. Jiří Matoušek and Aleksandar Nikolov. Combinatorial discrepancy for boxes via the ellipsoid-infinity norm. To appear in SoCG 15., 2014. Google Scholar
  33. S. Muthukrishnan and A. Nikolov. Optimal private halfspace counting via discrepancy. In STOC '12: Proceedings of the 44th symposium on Theory of Computing, pages 1285-1292, New York, NY, USA, 2012. ACM. Google Scholar
  34. A. Newman, O. Neiman, and A. Nikolov. Beck’s three permutations conjecture: A counterexample and some consequences. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 253-262, 2012. Google Scholar
  35. A. Nikolov and K. Talwar. Approximating hereditary discrepancy via small width ellipsoids. Preprint arXiv:1311.6204, 2013. Google Scholar
  36. A. Nikolov and K. Talwar. On the hereditary discrepancy of homogeneous arithmetic progressions. To Appear in Proceedings of AMS, 2013. Google Scholar
  37. A. Nikolov, K. Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proc. 45th ACM Symposium on Theory of Computing (STOC), Palo Alto, California, USA, pages 351-360, 2013. Full version to appear in SIAM Journal on Computing as The Geometry of Differential Privacy: the Small Database and Approximate Cases. Google Scholar
  38. D. Pálvölgyi. Indecomposable coverings with concave polygons. Discrete Comput. Geom., 44(3):577-588, 2010. Google Scholar
  39. K. F. Roth. On irregularities of distribution. Mathematika, 1:73-79, 1954. Google Scholar
  40. Thomas Rothvoß. Constructive discrepancy minimization for convex sets. CoRR, abs/1404.0339, 2014. To Appear in FOCS 2014. Google Scholar
  41. W. M. Schmidt. On irregularities of distribution VII. Acta Arith., 21:45-50, 1972. Google Scholar
  42. A. Seeger. Calculus rules for combinations of ellipsoids and applications. Bull. Australian Math. Soc., 47(01):1-12, 1993. Google Scholar
  43. J. Spencer. Ten Lectures on the Probabilistic Method. CBMS-NSF. SIAM, Philadelphia, PA, 1987. Google Scholar
  44. A. Srinivasan. Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. In Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, pages 692-701, 1997. Google Scholar
  45. G. Strang and S. MacNamara. Functions of difference matrices are Toeplitz plus Hankel. SIAM Review, 2014. To appear. Google Scholar
  46. Nicole Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1989. Google Scholar
  47. R. Vershynin. John’s decompositions: Selecting a large part. Israel Journal of Mathematics, 122(1):253-277, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact