{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005765,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","funder":[{"name":"NSF","award":["DMS-2347954"],"award-info":[{"award-number":["DMS-2347954"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718238","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"795-805","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Matrix Chaos Inequalities and Chaos of Combinatorial Type"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7331-7557","authenticated-orcid":false,"given":"Afonso S.","family":"Bandeira","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7993-1846","authenticated-orcid":false,"given":"Kevin","family":"Lucca","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8555-9117","authenticated-orcid":false,"given":"Petar","family":"Nizic-Nikolac","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4026-8100","authenticated-orcid":false,"given":"Ramon","family":"van Handel","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJP567"},{"key":"e_1_3_2_1_2_1","unstructured":"Kwangjun Ahn Dhruv Medarametla and Aaron Potechin. 2016. Graph matrices: Norm bounds and applications. arXiv preprint arXiv:1604.03423."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-023-01204-6"},{"key":"e_1_3_2_1_4_1","unstructured":"A. S. Bandeira G. Cipolloni D. Schr\u00f6der and R. van Handel. 2024. Matrix concentration inequalities and free probability II. Two-sided bounds and applications. Preprint arxiv:2406.11453"},{"key":"e_1_3_2_1_5_1","unstructured":"Afonso S. Bandeira Kevin Lucca Petar Nizi\u0107-Nikolac and Ramon van Handel. [n. d.]. Matrix Chaos Inequalities. Forthcoming."},{"key":"e_1_3_2_1_6_1","unstructured":"Afonso S. Bandeira Kevin Lucca Petar Nizi\u0107-Nikolac and Ramon van Handel. 2024. Matrix Chaos Inequalities and Chaos of Combinatorial Type. arxiv:2412.18468. arxiv:2412.18468"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.30757\/alea.v21-69"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-024-00692-9"},{"key":"e_1_3_2_1_10_1","unstructured":"Wenjun Cai and Aaron Potechin. 2022. On mixing distributions via random orthogonal matrices and the spectrum of the singular values of multi-z shaped graph matrices. arXiv preprint arXiv:2206.02224."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_18"},{"key":"e_1_3_2_1_12_1","volume-title":"Decoupling: From Dependence to Independence","author":"de la Pe\u00f1a V.","year":"2012","unstructured":"V. de la Pe\u00f1a and E. Gin\u00e9. 2012. Decoupling: From Dependence to Independence. Springer New York. isbn:9781461205371 lccn:98030322 https:\/\/books.google.ch\/books?id=aW7jBwAAQBAJ"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-021-01084-8"},{"key":"e_1_3_2_1_14_1","unstructured":"Zhou Fan and Renyuan Ma. 2024. Kronecker-product random matrices and a matrix least squares problem. arXiv preprint arXiv:2406.00961."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-93-07134-7"},{"volume-title":"Statistical Inference and the Sum of Squares Method. Dissertation","author":"Hopkins Samuel","key":"e_1_3_2_1_16_1","unstructured":"Samuel Hopkins. 2018. Statistical Inference and the Sum of Squares Method. Dissertation, Cornell University, https:\/\/api.semanticscholar.org\/CorpusID:247858642"},{"key":"e_1_3_2_1_17_1","volume-title":"Conference on Learning Theory. 956\u20131006","author":"Hopkins Samuel B","year":"2015","unstructured":"Samuel B Hopkins, Jonathan Shi, and David Steurer. 2015. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory. 956\u20131006."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.78"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP771"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806795"},{"key":"e_1_3_2_1_21_1","first-page":"167","article-title":"Solutions to some functional equations and their applications to characterization of probability distributions","volume":"30","author":"Khatri C. G.","year":"1968","unstructured":"C. G. Khatri and C. Radhakrishna Rao. 1968. Solutions to some functional equations and their applications to characterization of probability distributions. Sankhy\u0101 Ser. A, 30 (1968), 167\u2013180. issn:0581-572X","journal-title":"Sankhy\u0101 Ser. A"},{"key":"e_1_3_2_1_22_1","unstructured":"C\u00e9cilia Lancien and Pierre Youssef. 2023. A note on quantum expanders. arXiv preprint arXiv:2302.07772."},{"key":"e_1_3_2_1_23_1","volume-title":"Polynomial-Time Tensor Decompositions with Sum-of-Squares. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 438\u2013446","author":"Ma Tengyu","year":"2016","unstructured":"Tengyu Ma, Jonathan Shi, and David Steurer. 2016. Polynomial-Time Tensor Decompositions with Sum-of-Squares. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 438\u2013446. https:\/\/api.semanticscholar.org\/CorpusID:4854055"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP892"},{"key":"e_1_3_2_1_25_1","first-page":"018","volume-title":"Leibniz Int. Proc. Inform.","volume":"40","author":"Medarametla Dhruv","year":"2016","unstructured":"Dhruv Medarametla and Aaron Potechin. 2016. Bounds on the norms of uniform low degree graph matrices. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques (LIPIcs. Leibniz Int. Proc. Inform., Vol. 60). Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 40, 26. isbn:978-3-95977-018-7"},{"key":"e_1_3_2_1_26_1","volume-title":"2015 ACM Symposium on Theory of Computing. ACM","author":"Meka Raghu","year":"2015","unstructured":"Raghu Meka, Aaron Potechin, and Avi Wigderson. 2015. Sum-of-squares lower bounds for planted clique. In STOC\u201915\u2014Proceedings of the 2015 ACM Symposium on Theory of Computing. ACM, New York, 87\u201396. isbn:978-1-4503-3536-2"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-ejp392"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107360235"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1069-0"},{"key":"e_1_3_2_1_30_1","volume-title":"Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. ArXiv, abs\/2011.04253","author":"Potechin Aaron","year":"2020","unstructured":"Aaron Potechin and Goutham Rajendran. 2020. Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. ArXiv, abs\/2011.04253 (2020), https:\/\/api.semanticscholar.org\/CorpusID:226282041"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch138"},{"volume-title":"SPARS\u201909 - Signal Processing with Adaptive Sparse Structured Representations, R\u00e9mi Gribonval (Ed.).","author":"Rauhut Holger","key":"e_1_3_2_1_32_1","unstructured":"Holger Rauhut. 2009. Circulant and Toeplitz Matrices in Compressed Sensing. In SPARS\u201909 - Signal Processing with Adaptive Sparse Structured Representations, R\u00e9mi Gribonval (Ed.). Saint Malo, France. https:\/\/inria.hal.science\/inria-00369580"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.08.010"},{"key":"e_1_3_2_1_34_1","volume-title":"An introduction to matrix concentration inequalities. Foundations and Trends\u00ae in Machine Learning, 8, 1-2","author":"Tropp Joel A","year":"2015","unstructured":"Joel A Tropp. 2015. An introduction to matrix concentration inequalities. Foundations and Trends\u00ae in Machine Learning, 8, 1-2 (2015), 1\u2013230."},{"key":"e_1_3_2_1_35_1","unstructured":"Madhur Tulsiani and June Wu. 2024. Simple Norm Bounds for Polynomial Random Matrices via Decoupling. arXiv preprint arXiv:2412.07936."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978315.10"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:45:38Z","timestamp":1750693538000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":36,"alternative-id":["10.1145\/3717823.3718238","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718238","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}