On the hereditary discrepancy of homogeneous arithmetic progressions
HTML articles powered by AMS MathViewer
- by Aleksandar Nikolov and Kunal Talwar PDF
- Proc. Amer. Math. Soc. 143 (2015), 2857-2863 Request permission
Abstract:
We show that the hereditary discrepancy of homogeneous arithmetic progressions is bounded from below by $n^{1/O(\log \log n)}$. This bound is tight up to a constant in the exponent. Our lower bound goes via an exponential lower bound on the discrepancy of set systems of subcubes of the boolean cube $\{0, 1\}^d$.References
- Multiple Authors, Erdős discrepancy problem: Polymath wiki, http://michaelnielsen.org/polymath1/index.php?title=The\_Erd\%C5\%91s\_discrepancy\_problem.
- B. Chazelle and A. Lvov, The discrepancy of boxes in higher dimension, Discrete Comput. Geom. 25 (2001), no. 4, 519–524. The Micha Sharir birthday issue. MR 1838418, DOI 10.1007/s00454-001-0014-2
- B. Chazelle and A. Lvov, A trace bound for the hereditary discrepancy, Discrete Comput. Geom. 26 (2001), no. 2, 221–231. ACM Symposium on Computational Geometry (Hong Kong, 2000). MR 1843438, DOI 10.1145/336154.336179
- Paul Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), 291–300. MR 98702
- Steven Finch, Two-colorings of positive integers, http://www.people.fas.harvard.edu/~sfinch/csolve/ec.pdf.
- Gil Kalai, Erdős discrepancy problem 22, http://gowers.wordpress.com/2012/08/22/edp22-first-guest-post-from-gil-kalai/, 09 2012.
- Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman, The price of privately releasing contingency tables and the spectra of random matrices with correlated rows, STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 775–784. MR 2743327
- Boris Konev and Alexei Lisitsa, A sat attack on the erdős discrepancy conjecture, CoRR abs/1402.2184 (2014).
- L. Lovász, J. Spencer, and K. Vesztergombi, Discrepancy of set-systems and matrices, European J. Combin. 7 (1986), no. 2, 151–160. MR 856328, DOI 10.1016/S0195-6698(86)80041-5
- S. Muthukrishnan and Aleksandar Nikolov, Optimal private halfspace counting via discrepancy, STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 1285–1292. MR 2961660, DOI 10.1145/2213977.2214090
- Mark Rudelson, Row products of random matrices, Adv. Math. 231 (2012), no. 6, 3199–3231. MR 2980497, DOI 10.1016/j.aim.2012.08.010
Additional Information
- Aleksandar Nikolov
- Affiliation: Department of Computer Science, Rutgers University, Piscataway, New Jersey 08854
- Address at time of publication: Microsoft Research, Redmond, Washington 98052
- Email: alenik@microsoft.com
- Kunal Talwar
- Affiliation: Microsoft Research, Mountain View, California 94043
- Address at time of publication: Google, Mountain View, California 94043
- Email: kunal@kunaltalwar.org
- Received by editor(s): September 23, 2013
- Received by editor(s) in revised form: March 27, 2014
- Published electronically: February 27, 2015
- Communicated by: Harm Derksen
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 143 (2015), 2857-2863
- MSC (2010): Primary 11K38; Secondary 11B25
- DOI: https://doi.org/10.1090/S0002-9939-2015-12545-2
- MathSciNet review: 3336610