A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent
by Daniel Dadush, Haotian Jiang, and Victor Reis
Theory of Computing, Volume 22(2111), pp. 1-25, 2026
Bibliography with links to cited articles
[1] Rudolf Ahlswede and Andreas Winter: Strong converse for identification via quantum channels. IEEE Trans. Inform. Theory, 48(3):569–579, 2002. [doi:10.1109/18.985947, arXiv:quant-ph/0012127]
[2] Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman: Asymptotic geometric analysis, Part I. Amer. Math. Soc., 2015. [doi:10.1090/surv/202]
[3] Keith Ball, Eric A. Carlen, and Elliott H. Lieb: Sharp uniform convexity and smoothness inequalities for trace norms. Inventiones Math., 115(1):463–482, 1994. [doi:10.1007/BF01231769]
[4] Wojciech Banaszczyk: Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Struct. Algor., 12(4):351–360, 1998. [doi:10.1002/(SICI)1098-2418(199807)12:4¡351::AID-RSA3¿3.0.CO;2-S]
[5] Afonso S. Bandeira, March T. Boedihardjo, and Ramon van Handel: Matrix concentration inequalities and free probability. Inventiones Math., 234(1):419–487, 2023. [doi:10.1007/s00222-023-01204-6, arXiv:2108.06312]
[6] Nikhil Bansal: Constructive algorithms for discrepancy minimization. In Proc. 51st FOCS, pp. 3–10. IEEE Comp. Soc., 2010. [doi:10.1109/FOCS.2010.7]
[7] 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]
[8] 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, arXiv:1605.02882]
[9] Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett: The Gram–Schmidt walk: A cure for the Banaszczyk blues. Theory of Computing, 15(21):1–27, 2019. Preliminary version in STOC’18. [doi:10.4086/toc.2019.v015a021]
[10] 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]
[11] Nikhil Bansal, Haotian Jiang, and Raghu Meka: Resolving matrix Spencer conjecture up to poly-logarithmic rank. SIAM J. Comput., pp. STOC23:57–67, 2024. Preliminary version in STOC’23. [doi:10.1137/23M1592201, arXiv:2208.11286]
[12] Nikhil Bansal and Viswanath Nagarajan: Approximation-friendly discrepancy rounding. In Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, editors, A Journey Through Discrete Mathematics, pp. 89–114. Springer, 2017. Preliminary version in IPCO’16. [doi:10.1007/978-3-319-44479-6_4, arXiv:1512.02254]
[13] 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]
[14] Sébastien Bubeck: Convex optimization: Algorithms and complexity. Found. Trends Mach. Learning, 8(3–4):231–357, 2015. [doi:10.1561/2200000050, arXiv:1405.4980]
[15] Eric A. Carlen: A remainder term for Hölder’s inequality for matrices and quantum entropy inequalities. Archiv der Mathematik, 109(4):365–371, 2017. [doi:10.1007/s00013-017-1066-8, arXiv:1605.04581]
[16] Bernard Chazelle: The Discrepancy Method: Randomness and Complexity. Cambridge Univ. Press, 2000. [doi:10.1017/CBO9780511626371]
[17] 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]
[18] Daniel Dadush, Haotian Jiang, and Victor Reis: A new framework for matrix discrepancy: Partial coloring bounds via mirror descent. In Proc. 54th STOC, pp. 649–658. ACM Press, 2022. [doi:10.1145/3519935.3519967]
[19] Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, and Nicole Tomczak-Jaegermann: Balancing vectors in any norm. In Proc. 59th FOCS, pp. 1–10. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00010]
[20] Ronen Eldan and Mohit Singh: Efficient algorithms for discrepancy minimization in convex sets. Random Struct. Algor., 53(2):289–307, 2018. [doi:10.1002/rsa.20763, arXiv:1409.2913]
[21] Efim Davydovich Gluskin: Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces. Sbornik Math., 64(1):85–96, 1989. [doi:10.1070/SM1989v064n01ABEH003295]
[22] Aicke Hinrichs, Joscha Prochno, and Jan Vybíral: Entropy numbers of embeddings of Schatten classes. J. Functional Anal., 273(10):3241–3261, 2017. [doi:10.1016/j.jfa.2017.08.008, arXiv:1612.08105]
[23] Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty: Matrix discrepancy from quantum communication. In Proc. 54th STOC, pp. 637–648. ACM Press, 2022. [doi:10.1145/3519935.3519954]
[24] Hermann König and Vitali D. Milman: On the covering numbers of convex bodies. In Joram Lindenstrauss and Vitali D. Milman, editors, Geometrical Aspects of Functional Analysis, pp. 82–95. Springer, 1987. [doi:10.1007/BFb0078138]
[25] Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss: Deterministic discrepancy minimization via the multiplicative weight update method. In Proc. 19th Integer Prog. Combinat. Optim. (IPCO’17), volume 10328 of LNCS, pp. 380–391. Springer, 2017. [doi:10.1007/978-3-319-59250-3_31, arXiv:1611.08752]
[26] Shachar Lovett and Raghu Meka: Constructive discrepancy minimization by walking on the edges. SIAM J. Comput., 44(5):1573–1582, 2015. [doi:10.1137/130929400, arXiv:1203.5747]
[27] Françoise Lust-Piquard and Gilles Pisier: Non commutative Khintchine and Paley inequalities. Arkiv för Mat., 29(1–2):241–260, 1991. [doi:10.1007/BF02384340]
[28] Jiří Matoušek: Geometric Discrepancy: An Illustrated Guide. Volume 18 of Algorithms and Combinatorics. Springer, 1999. [doi:10.1007/978-3-642-03942-3]
[29] Mark W. Meckes: On the spectral norm of a random Toeplitz matrix. Electr. Comm. Probability, 12:315–325, 2007. [doi:10.1214/ECP.v12-1313]
[30] Raghu Meka: Discrepancy and beating the union bound, 2014. Windows on Theory.
[31] Arkadi Semenovich Nemirovski and David Borisovich Yudin: Problem Complexity and Method Efficiency in Optimization. Wiley, 1983. Link at GaTech.
[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]
[33] Gilles Pisier: Introduction to Operator Space Theory. Volume 294 of LMS Lecture Notes. Cambridge Univ. Press, 2003. [doi:10.1017/CBO9781107360235]
[34] Victor Reis and Thomas Rothvoss: Vector balancing in Lebesgue spaces. Random Struct. Algor., 62(3):667–688, 2023. [doi:10.1002/rsa.21113, arXiv:2007.05634]
[35] Thomas Rothvoss: Approximating bin packing within O(log OPT ⋅ log log OPT) bins. In Proc. 54th FOCS, pp. 20–29. IEEE Comp. Soc., 2013. [doi:10.1109/FOCS.2013.11]
[36] Thomas Rothvoss: Constructive discrepancy minimization for convex sets. SIAM J. Comput., 46(1):224–234, 2017. [doi:10.1137/141000282]
[37] Thomas Royen: A simple proof of the Gaussian correlation conjecture extended to some multivariate gamma distributions. Far East J. Theor. Stat., 48(2):139–145, 2014. Available at publisher’s website. [arXiv:1408.1028]
[38] Zbyněk Šidák: Rectangular confidence regions for the means of multivariate normal distributions. J. Amer. Statistical Assoc., 62(318):626–633, 1967. [doi:10.1080/01621459.1967.10482935]
[39] Joel Spencer: Six standard deviations suffice. Trans. AMS, 289(2):679–706, 1985. [doi:10.1090/S0002-9947-1985-0784009-0]
[40] Roman Vershynin: High-Dimensional Probability: An Introduction with Applications in Data Science. Volume 47 of Cambr. Ser. in Statistical and Probabilistic Mathematics. Cambridge Univ. Press, 2018. [doi:10.1017/9781108231596]
[41] Nik Weaver: The Kadison–Singer problem in discrepancy theory. Discr. Math., 278(1–3):227–239, 2004. [doi:10.1016/S0012-365X(03)00253-X]
[42] Anastasios Zouzias: A matrix hyperbolic cosine algorithm and applications. In Proc. 39th Internat. Colloq. on Automata, Languages, and Programming (ICALP’12), pp. 846–858. Springer, 2012. [doi:10.1007/978-3-642-31594-7_71, arXiv:1103.2793]
