{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:59Z","timestamp":1750220279316,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520060","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"568-581","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Matrix anti-concentration inequalities with applications"],"prefix":"10.1145","author":[{"given":"Zipei","family":"Nie","sequence":"first","affiliation":[{"name":"Huawei, France"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Noga Alon. 2020. Problems and results in Extremal Combinatorics\u2013IV. arXiv preprint arXiv:2009.12692.  Noga Alon. 2020. Problems and results in Extremal Combinatorics\u2013IV. arXiv preprint arXiv:2009.12692."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/31.3.253"},{"key":"e_1_3_2_1_3_1","unstructured":"LB Beasley. 1987. Nullspaces of spaces of matrices of bounded rank. Current trends in matrix theory 45\u201350.  LB Beasley. 1987. Nullspaces of spaces of matrices of bounded rank. Current trends in matrix theory 45\u201350."},{"key":"e_1_3_2_1_4_1","unstructured":"S\u00edlvia Casacuberta and Rasmus Kyng. 2021. Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. arXiv preprint arXiv:2106.09830.  S\u00edlvia Casacuberta and Rasmus Kyng. 2021. Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. arXiv preprint arXiv:2106.09830."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-017-0778-9"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-06-13527-5"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02038756"},{"key":"e_1_3_2_1_8_1","unstructured":"Xiaoyu Dong. 2021. The Smallest Singular Value of a Shifted Random Matrix. arXiv preprint arXiv:2108.05413.  Xiaoyu Dong. 2021. The Smallest Singular Value of a Shifted Random Matrix. arXiv preprint arXiv:2108.05413."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1145768.1145785"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277548.1277569"},{"key":"e_1_3_2_1_11_1","series-title":"SIAM journal on matrix analysis and applications, 9, 4","volume-title":"Eigenvalues and condition numbers of random matrices","author":"Edelman Alan","year":"1988","unstructured":"Alan Edelman . 1988. Eigenvalues and condition numbers of random matrices . SIAM journal on matrix analysis and applications, 9, 4 ( 1988 ), 543\u2013560. Alan Edelman. 1988. Eigenvalues and condition numbers of random matrices. SIAM journal on matrix analysis and applications, 9, 4 (1988), 543\u2013560."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00531753"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/12844"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-37.1.10"},{"key":"e_1_3_2_1_15_1","unstructured":"Mehrdad Ghadiri Richard Peng and Santosh S Vempala. 2021. Sparse Regression Faster than d^\u03c9. arXiv preprint arXiv:2109.11537.  Mehrdad Ghadiri Richard Peng and Santosh S Vempala. 2021. Sparse Regression Faster than d^\u03c9. arXiv preprint arXiv:2109.11537."},{"key":"e_1_3_2_1_16_1","unstructured":"Shaoming Guo Changkeun Oh Ruixiang Zhang and Pavel Zorin-Kranich. 2020. Decoupling inequalities for quadratic forms. arXiv preprint arXiv:2011.09451.  Shaoming Guo Changkeun Oh Ruixiang Zhang and Pavel Zorin-Kranich. 2020. Decoupling inequalities for quadratic forms. arXiv preprint arXiv:2011.09451."},{"key":"e_1_3_2_1_17_1","unstructured":"Vishesh Jain Ashwin Sah and Mehtaab Sawhney. 2020. On the smoothed analysis of the smallest singular value with discrete noise. arXiv preprint arXiv:2009.01699.  Vishesh Jain Ashwin Sah and Mehtaab Sawhney. 2020. On the smoothed analysis of the smallest singular value with discrete noise. arXiv preprint arXiv:2009.01699."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.3150\/15-BEJ730"},{"key":"e_1_3_2_1_19_1","first-page":"12991","article-title":"Bounding the smallest singular value of a random matrix without concentration","volume":"2015","author":"Koltchinskii Vladimir","year":"2015","unstructured":"Vladimir Koltchinskii and Shahar Mendelson . 2015 . Bounding the smallest singular value of a random matrix without concentration . International Mathematics Research Notices , 2015 , 23 (2015), 12991 \u2013 13008 . Vladimir Koltchinskii and Shahar Mendelson. 2015. Bounding the smallest singular value of a random matrix without concentration. International Mathematics Research Notices, 2015, 23 (2015), 12991\u201313008.","journal-title":"International Mathematics Research Notices"},{"key":"e_1_3_2_1_20_1","first-page":"7","article-title":"On the determinant of (0-1) matrices","volume":"2","author":"Koml\u00f3s J\u00e1nos","year":"1967","unstructured":"J\u00e1nos Koml\u00f3s . 1967 . On the determinant of (0-1) matrices . Studia Scientiarium Mathematicarum Hungarica , 2 (1967), 7 \u2013 21 . J\u00e1nos Koml\u00f3s. 1967. On the determinant of (0-1) matrices. Studia Scientiarium Mathematicarum Hungarica, 2 (1967), 7\u201321.","journal-title":"Studia Scientiarium Mathematicarum Hungarica"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/682"},{"key":"e_1_3_2_1_22_1","volume-title":"The smallest singular value of heavy-tailed not necessarily iid random matrices via random rounding. Journal d\u2019Analyse Math\u00e9matique, 145, 1","author":"Livshyts Galyna V","year":"2021","unstructured":"Galyna V Livshyts . 2021. The smallest singular value of heavy-tailed not necessarily iid random matrices via random rounding. Journal d\u2019Analyse Math\u00e9matique, 145, 1 ( 2021 ), 257\u2013306. Galyna V Livshyts. 2021. The smallest singular value of heavy-tailed not necessarily iid random matrices via random rounding. Journal d\u2019Analyse Math\u00e9matique, 145, 1 (2021), 257\u2013306."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1481"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v17-2165"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0738-9"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Richard Peng and Santosh Vempala. 2020. Solving Sparse Linear Systems Faster than Matrix Multiplication. arXiv preprint arXiv:2007.10254.  Richard Peng and Santosh Vempala. 2020. Solving Sparse Linear Systems Faster than Matrix Multiplication. arXiv preprint arXiv:2007.10254.","DOI":"10.1137\/1.9781611976465.31"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.31"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-018-1732-y"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2008.168.575"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.01.010"},{"key":"e_1_3_2_1_31_1","volume-title":"Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62, 12","author":"Rudelson Mark","year":"2009","unstructured":"Mark Rudelson and Roman Vershynin . 2009. Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62, 12 ( 2009 ), 1707\u20131739. Mark Rudelson and Roman Vershynin. 2009. Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62, 12 (2009), 1707\u20131739."},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the International Congress of Mathematicians 2010 (ICM 2010)","volume":"1602","author":"Rudelson Mark","year":"2010","unstructured":"Mark Rudelson and Roman Vershynin . 2010 . Non-asymptotic theory of random matrices: extreme singular values . In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II\u2013IV: Invited Lectures. 1576\u2013 1602 . Mark Rudelson and Roman Vershynin. 2010. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II\u2013IV: Invited Lectures. 1576\u20131602."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436202"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-015-1198-0"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2016.03.051"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP760"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(91)90002-F"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.169.595"},{"key":"e_1_3_2_1_40_1","volume-title":"Smooth analysis of the condition number and the least singular value. Mathematics of computation, 79, 272","author":"Tao Terence","year":"2010","unstructured":"Terence Tao and Van Vu. 2010. Smooth analysis of the condition number and the least singular value. Mathematics of computation, 79, 272 ( 2010 ), 2333\u20132352. Terence Tao and Van Vu. 2010. Smooth analysis of the condition number and the least singular value. Mathematics of computation, 79, 272 (2010), 2333\u20132352."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2716-x"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20920"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1287-8"},{"key":"e_1_3_2_1_44_1","volume-title":"User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12, 4","author":"Tropp Joel A","year":"2012","unstructured":"Joel A Tropp . 2012. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12, 4 ( 2012 ), 389\u2013434. Joel A Tropp. 2012. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12, 4 (2012), 389\u2013434."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Joel A Tropp. 2015. An introduction to matrix concentration inequalities. arXiv preprint arXiv:1501.01571.  Joel A Tropp. 2015. An introduction to matrix concentration inequalities. arXiv preprint arXiv:1501.01571.","DOI":"10.1561\/9781601988393"},{"key":"e_1_3_2_1_46_1","volume-title":"Spectral norm of products of random and deterministic matrices. Probability theory and related fields, 150, 3","author":"Vershynin Roman","year":"2011","unstructured":"Roman Vershynin . 2011. Spectral norm of products of random and deterministic matrices. Probability theory and related fields, 150, 3 ( 2011 ), 471\u2013509. Roman Vershynin. 2011. Spectral norm of products of random and deterministic matrices. Probability theory and related fields, 150, 3 (2011), 471\u2013509."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20429"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0226281-1"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v19-3807"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v20-4089"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2016.03.048"},{"key":"e_1_3_2_1_52_1","unstructured":"Nikita Zhivotovskiy. 2021. Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle. arXiv preprint arXiv:2108.08198.  Nikita Zhivotovskiy. 2021. Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle. arXiv preprint arXiv:2108.08198."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520060","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":52,"alternative-id":["10.1145\/3519935.3520060","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520060","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}