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¿3.0.co;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:https://doi.org/10.1137/130929400, 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]