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]