The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues
by Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
Theory of Computing, Volume 15(21), pp. 1-27, 2019
Bibliography with links to cited articles
[1] 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]
[2] Wojciech Banaszczyk: On series of signed vectors and their rearrangements. Random Structures Algorithms, 40(3):301–316, 2012. [doi:10.1002/rsa.20373]
[3] 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]
[4] Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, and Shi Li: Better algorithms and hardness for broadcast scheduling via a discrepancy approach. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 55–71. SIAM, 2014. [doi:10.1137/1.9781611973402.5]
[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:https://doi.org/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] Nikhil Bansal and Shashwat Garg: Algorithmic discrepancy beyond partial coloring. In Proc. 49th STOC, pp. 914–926. ACM Press, 2017. [doi:10.1145/3055399.3055490, arXiv:1611.01805]
[8] Nikhil Bansal and Viswanath Nagarajan: Approximation-friendly discrepancy rounding. In Proc. 18th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’16), pp. 375–386. Springer, 2016. [doi:10.1007/978-3-319-33461-5_31, arXiv:1512.02254]
[9] Imre Bárány: On the power of linear dependencies. In Building Bridges (M. Grötschel and G. O. H. Katona, eds.), volume 19 of Bolyai Soc. Math. Studies, pp. 31–45. Springer, 2008. [doi:10.1007/978-3-540-85221-6_1]
[10] 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]
[11] 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]
[12] 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]
[13] Moses Charikar, Alantha Newman, and Aleksandar Nikolov: Tight hardness results for minimizing discrepancy. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 1607–1614. SIAM, 2011. [doi:10.1137/1.9781611973082.124]
[14] Bernard Chazelle: The Discrepancy Method: Randomness and Complexity. Cambridge Univ. Press, 2000. [doi:10.1017/CBO9780511626371]
[15] Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov: Towards a constructive version of Banaszczyk’s vector balancing theorem. Theory of Computing, 15(15):1–58, 2019. Preliminary version in RANDOM’16. [doi:10.4086/toc.2019.v015a015]
[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]
[17] David A. Freedman: On tail probabilities for martingales. Ann. Probab., 3(1):100–118, 1975. [doi:10.1214/aop/1176996452]
[18] Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan: Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324–360, 2006. Preliminary version in FOCS’02. [doi:10.1145/1147954.1147956]
[19] Efim Davydovich Gluskin: Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces. Sbornik: Mathematics, 64(1):85–96, 1989. [doi:10.1070/SM1989v064n01ABEH003295]
[20] 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]
[21] Kasper Green Larsen: On range searching in the group model and combinatorial discrepancy. SIAM J. Comput., 43(2):673–686, 2014. Preliminary version in FOCS’11. [doi:10.1137/120865240]
[22] Lap-Chi Lau, R. Ravi, and Mohit Singh: Iterative Methods in Combinatorial Optimization. Cambridge Univ. Press, 2011. [doi:10.1017/CBO9780511977152]
[23] 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]
[24] László Lovász, Joel H. Spencer, and Katalin Vesztergombi: Discrepancy of set-systems and matrices. European J. Combinatorics, 7(2):151–160, 1986. [doi:10.1016/S0195-6698(86)80041-5]
[25] 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:10.1137/130929400, arXiv:1203.5747]
[26] Jiří Matoušek: An Lp version of the Beck-Fiala conjecture. European J. Combinatorics, 19(2):175–182, 1998. [doi:10.1006/eujc.1997.0162]
[27] Jiří Matoušek: Geometric Discrepancy: An Illustrated Guide. Springer, 2009. [doi:10.1007/978-3-642-03942-3]
[28] Jiří Matoušek, Aleksandar Nikolov, and Kunal Talwar: Factorization norms and hereditary discrepancy. Internat. Mathematics Research Notices, rny033, 2018. [doi:10.1093/imrn/rny033, arXiv:1408.1376]
[29] Aleksandar Nikolov: The Komlós conjecture holds for vector colorings, 2013. [arXiv:1301.4039]
[30] Aleksandar Nikolov: New Computational Aspects of Discrepancy Theory. Ph. D. thesis, Rutgers University, 2014. [doi:10.7282/T3RN3749]
[31] Aleksandar Nikolov: Tighter bounds for the discrepancy of boxes and polytopes. Mathematika, 63(3):1091–1113, 2017. [doi:10.1112/S0025579317000250, arXiv:1701.05532]
[32] Aleksandar Nikolov, Kunal Talwar, and Li Zhang: The geometry of differential privacy: The small database and approximate cases. SIAM J. Comput., 45(2):575–616, 2016. Preliminary version in STOC’13. [doi:10.1137/130938943, arXiv:1212.0297]
[33] Thomas Rothvoss: Better bin packing approximations via discrepancy theory. SIAM J. Comput., 45(3):930–946, 2016. Preliminary version in FOCS’13. [doi:10.1137/140955367, arXiv:1301.4010]
[34] 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]
[35] Joel H. Spencer: Six standard deviations suffice. Trans. Amer. Math. Soc., 289(2):679–706, 1985. [doi:10.1090/S0002-9947-1985-0784009-0]
[36] Joel H. Spencer: Ten Lectures on the Probabilistic Method. SIAM, 1987. [doi:10.1137/1.9781611970074]
[37] Aravind Srinivasan: Distributions on level-sets with applications to approximation algorithms. In Proc. 42nd FOCS, pp. 588–597. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959935]
[38] Michel Talagrand: The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. Springer, 2005. [doi:10.1007/3-540-27499-5]