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]