Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

by Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov

Theory of Computing, Volume 15(15), pp. 1-58, 2019

Bibliography with links to cited articles

[1]   Milton Abramowitz and Irene A. Stegun, eds.: Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tables. Dover Publ., 1992. Reprint of the 1972 edition [LINK to original].

[2]   Wojciech Banaszczyk: Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures Algorithms, 12(4):351–360, 1998. [doi:10.1002/(sici)1098-2418(199807)12:4ˇ351::aid-rsa3ż;2-s]

[3]   Wojciech Banaszczyk: On series of signed vectors and their rearrangements. Random Structures Algorithms, 40(3):301–316, 2012. [doi:10.1002/rsa.20373]

[4]   Nikhil Bansal: Constructive algorithms for discrepancy minimization. In Proc. 51st FOCS, pp. 3–10. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.7, arXiv:1002.2259]

[5]   Nikhil Bansal, Daniel Dadush, and Shashwat Garg: An algorithm for Komlós conjecture matching Banaszczyk’s bound. SIAM J. Comput., 48(2):534–553, 2019. Preliminary version in FOCS’16. [doi:10.1137/17M1126795]

[6]   Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett: The Gram-Schmidt walk: a cure for the Banaszczyk blues. In Proc. 50th STOC, pp. 587–597. ACM Press, 2018. [doi:10.1145/3188745.3188850]

[7]   Franck Barthe, Olivier Guédon, Shahar Mendelson, and Assaf Naor: A probabilistic approach to the geometry of the pn-ball. Ann. Probab., 33(2):480–513, 2005. [doi:10.1214/009117904000000874, arXiv:math/0503650]

[8]   József Beck: Roth’s estimate of the discrepancy of integer sequences is nearly sharp. Combinatorica, 1(4):319–325, 1981. [doi:10.1007/BF02579452]

[9]   József Beck and Tibor Fiala: “Integer-making” theorems. Discr. Appl. Math., 3(1):1–8, 1981. [doi:10.1016/0166-218X(81)90022-6]

[10]   Christer Borell: The Ehrhard inequality. C. R. Math. Acad. Sci. Paris, 337(10):663–666, 2003. [doi:10.1016/j.crma.2003.09.031]

[11]   Boris Bukh: An improvement of the Beck-Fiala theorem. Combin. Probab. Comput., 25(3):380–398, 2016. [doi:10.1017/S0963548315000140, arXiv:1306.6081]

[12]   Bernard Chazelle: The Discrepancy Method: Randomness and Complexity. Cambridge Univ. Press, 2000. [doi:10.1017/CBO9780511626371]

[13]    William Chen, Anand Srivastav, Giancarlo Travaglini, et al.: A Panorama of Discrepancy Theory. Springer, 2014. [doi:10.1007/978-3-319-04696-9]

[14]   Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov: Towards a constructive version of Banaszczyk’s vector balancing theorem. In Proc. 20th Internat. Workshop on Randomization and Computation (RANDOM’16), volume 60 of LIPIcs, pp. 28:1–28:12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.APPROX-RANDOM.2016.28]

[15]   Antoine Ehrhard: Symétrisation dans l’espace de Gauss. Math. Scand., 53(2):281–301, 1983. [doi:10.7146/math.scand.a-12035]

[16]   Ronen Eldan and Mohit Singh: Efficient algorithms for discrepancy minimization in convex sets. Random Structures Algorithms, 53(2):289–307, 2018. [doi:10.1002/rsa.20763, arXiv:1409.2913]

[17]   Esther Ezra and Shachar Lovett: On the Beck-Fiala conjecture for random set systems. Random Structures Algorithms, 54(4):665–675, 2019. Preliminary version in RANDOM’16. [doi:10.1002/rsa.20810, arXiv:1511.00583]

[18]   David A. Freedman: On tail probabilities for martingales. Ann. Probab., 3(1):100–118, 1975. [doi:10.1214/aop/1176996452]

[19]   Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh: Discrepancy without partial colorings. In Proc. 17th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’14), volume 28 of LIPIcs, pp. 258–273. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.258]

[20]   Rafał Latała and Krzysztof Oleszkiewicz: Gaussian measures of dilatations of convex symmetric sets. Ann. Probab., 27(4):1922–1938, 1999. [doi:10.1214/aop/1022874821]

[21]   Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss: Deterministic discrepancy minimization via the multiplicative weight update method. In Proc. 19th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’17), pp. 380–391. Springer, 2017. [doi:10.1007/978-3-319-59250-3_31, arXiv:1611.08752]

[22]   László Lovász, Joel H. Spencer, and Katalin Vesztergombi: Discrepancy of set-systems and matrices. European J. Combin., 7(2):151–160, 1986. [doi:10.1016/S0195-6698(86)80041-5]

[23]   Shachar Lovett and Raghu Meka: Constructive discrepancy minimization by walking on the edges. SIAM J. Comput., 44(5):1573–1582, 2015. Preliminary version in FOCS’12. [doi:, arXiv:1203.5747]

[24]   Jiří Matoušek: Geometric Discrepancy: An Illustrated Guide. Springer, 1999. [doi:10.1007/978-3-642-03942-3]

[25]   John von Neumann: Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100(1):295–320, 1928. [doi:10.1007/BF01448847]

[26]   Aleksandar Nikolov: The Komlós conjecture holds for vector colorings, 2013. [arXiv:1301.4039]

[27]   Aleksandar Nikolov: Tighter bounds for the discrepancy of boxes and polytopes. Mathematika, 63(3):1091–1113, 2017. [doi:10.1112/S0025579317000250, arXiv:1701.05532]

[28]   Aleksandar Nikolov and Kunal Talwar: Approximating hereditary discrepancy via small width ellipsoids. In Proc. 26th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’15), pp. 324–336. ACM Press, 2015. [doi:10.1137/1.9781611973730.24, arXiv:1311.6204]

[29]   Grigoris Paouris: Concentration of mass on convex bodies. Geom. Funct. Anal., 16(5):1021–1049, 2006. [doi:10.1007/s00039-006-0584-5]

[30]   Thomas Rothvoss: Constructive discrepancy minimization for convex sets. SIAM J. Comput., 46(1):224–234, 2017. Preliminary version in FOCS’14. [doi:10.1137/141000282, arXiv:1404.0339]

[31]   Joel Spencer: Six standard deviations suffice. Trans. Amer. Math. Soc., 289(2):679–706, 1985. [doi:10.1090/S0002-9947-1985-0784009-0]

[32]   Joel Spencer: Ten Lectures on the Probabilistic Method. Volume 52. SIAM, 1987. [doi:10.1137/1.9781611970074]

[33]   Aravind Srinivasan: Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. In Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’97), pp. 692–701. ACM Press, 1997. ACM DL.

[34]   Michel Talagrand: The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. Springer, 2005. [doi:10.1007/3-540-27499-5]