{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004993,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":75,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718188","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"822-832","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Tensor Concentration Inequalities: A Geometric Approach"],"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\/0000-0001-9706-4171","authenticated-orcid":false,"given":"Sivakanth","family":"Gopi","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7501-2247","authenticated-orcid":false,"given":"Haotian","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, USA"}]},{"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-0007-8314-0963","authenticated-orcid":false,"given":"Thomas","family":"Rothvoss","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, 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.1109\/TNSE.2014.2368716"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-023-02599-6"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.985947"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-28142-8"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585143"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2697055"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21861"},{"key":"e_1_3_2_1_8_1","volume-title":"Matrix concentration inequalities and free probability. Inventiones mathematicae, 234","author":"Bandeira Afonso S.","year":"2023","unstructured":"Afonso S. Bandeira, March Boedihardjo, and Ramon Handel. 2023. Matrix concentration inequalities and free probability. Inventiones mathematicae, 234 (2023), 419\u2013487. https:\/\/api.semanticscholar.org\/CorpusID:237048263"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Afonso S Bandeira Giorgio Cipolloni Dominik Schr\u00f6der and Ramon van Handel. 2024. Matrix Concentration Inequalities and Free Probability II. Two-sided Bounds and Applications. arXiv preprint arXiv:2406.11453 http:\/\/dx.doi.org\/10.48550\/arXiv.2406.11453 10.48550\/arXiv.2406.11453","DOI":"10.48550\/arXiv.2406.11453"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1408.6185"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585103"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-024-00692-9"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Jop Bri\u00ebt. 2016. On embeddings of \u2113 _1^k from locally decodable codes. arXiv preprint arXiv:1611.06385 http:\/\/dx.doi.org\/10.48550\/arXiv.1611.06385 10.48550\/arXiv.1611.06385","DOI":"10.48550\/arXiv.1611.06385"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Jop Bri\u00ebt Assaf Naor and Oded Regev. 2012. Locally decodable codes and the failure of cotype for projective tensor products. arXiv preprint arXiv:1208.0539 https:\/\/doi.org\/10.3934\/era.2012.19.120 10.3934\/era.2012.19.120","DOI":"10.3934\/era.2012.19.120"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-024-01254-4"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9135-7"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet"},{"key":"e_1_3_2_1_18_1","unstructured":"Stephane Dartois and Benjamin McKenna. 2024. Injective norm of real and complex random tensors I: From spin glasses to geometric entanglement. arXiv preprint arXiv:2404.03627 https:\/\/api.semanticscholar.org\/CorpusID:268889382"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4948-7_1"},{"key":"e_1_3_2_1_20_1","volume-title":"Conference on learning theory. 797\u2013842","author":"Ge Rong","year":"2015","unstructured":"Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. 2015. Escaping from saddle points\u2014online stochastic gradient for tensor decomposition. In Conference on learning theory. 797\u2013842. https:\/\/proceedings.mlr.press\/v40\/Ge15.pdf"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.829"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1453"},{"volume-title":"Locality in coding theory. Ph. D. Dissertation","author":"Gopi Sivakanth","key":"e_1_3_2_1_23_1","unstructured":"Sivakanth Gopi. 2018. Locality in coding theory. Ph. D. Dissertation. Princeton University. http:\/\/arks.princeton.edu\/ark:\/88435\/dsp01ng451m268"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45282-1_10"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519955"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"e_1_3_2_1_28_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. https:\/\/proceedings.mlr.press\/v40\/Hopkins15.html"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch89"},{"key":"e_1_3_2_1_30_1","volume-title":"Provable tensor factorization with missing data. Advances in Neural Information Processing Systems, 27","author":"Jain Prateek","year":"2014","unstructured":"Prateek Jain and Sewoong Oh. 2014. Provable tensor factorization with missing data. Advances in Neural Information Processing Systems, 27 (2014), https:\/\/dl.acm.org\/doi\/10.5555\/2968826.2968986"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00119"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649684"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585136"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAMPTA.2017.8024470"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649640"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00067"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-04-07800-1"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-018-0817-x"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/009117906000000421"},{"key":"e_1_3_2_1_40_1","unstructured":"Rafa\u0142 Lata\u0142a. 2024. On the spectral norm of Rademacher matrices. arXiv preprint arXiv:2405.13656 arxiv:2405.13656"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20212-4"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585165"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006580"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649650"},{"key":"e_1_3_2_1_45_1","unstructured":"Kevin Lucca. 2023. Norms of Random Multilinear Forms. ETH Research Collection https:\/\/www.research-collection.ethz.ch\/handle\/20.500.11850\/679603"},{"key":"e_1_3_2_1_46_1","first-page":"289","article-title":"In\u00e9galit\u00e9s de Khintchine dans C_p (1 < p < \u221e )","volume":"303","author":"Lust-Piquard Fran\u00e7oise","year":"1986","unstructured":"Fran\u00e7oise Lust-Piquard. 1986. In\u00e9galit\u00e9s de Khintchine dans C_p (1 < p < \u221e ). C. R. Math. Acad. Sci. Paris, 303, 7 (1986), 289\u2013292.","journal-title":"C. R. Math. Acad. Sci. Paris"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02384340"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1093\/jrsssa"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21748"},{"volume-title":"Aspects of multivariate statistical theory","author":"Muirhead Robb J","key":"e_1_3_2_1_51_1","unstructured":"Robb J Muirhead. 2009. Aspects of multivariate statistical theory. John Wiley & Sons. https:\/\/onlinelibrary.wiley.com\/doi\/abs\/10.1002\/9780470316559.oth1"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488618"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v15-1544"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21006"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1612.07728"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107360235"},{"key":"e_1_3_2_1_58_1","volume-title":"A statistical model for tensor PCA. Advances in neural information processing systems, 27","author":"Richard Emile","year":"2014","unstructured":"Emile Richard and Andrea Montanari. 2014. A statistical model for tensor PCA. Advances in neural information processing systems, 27 (2014), https:\/\/dl.acm.org\/doi\/10.5555\/2969033.2969150"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","unstructured":"Mark Rudelson. 1996. Random vectors in the isotropic position. arXiv preprint math\/9608208 https:\/\/doi.org\/10.48550\/arXiv.math\/9608208 10.48550\/arXiv.math\/9608208","DOI":"10.48550\/arXiv.math"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1998.3384"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000420X"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0330-5"},{"volume-title":"Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems","author":"Talagrand M.","key":"e_1_3_2_1_63_1","unstructured":"M. Talagrand. 2014. Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems. Springer Berlin Heidelberg. isbn:9783642540752 https:\/\/books.google.ch\/books?id=tfa5BAAAQBAJ"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Michel Talagrand. 2021. Upper and Lower Bounds for Stochastic Processes. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge \/ A Series of Modern Surveys in Mathematics https:\/\/api.semanticscholar.org\/CorpusID:123995577","DOI":"10.1007\/978-3-030-82595-9"},{"key":"e_1_3_2_1_65_1","first-page":"163","article-title":"The moduli of smoothness and convexity and the Rademacher averages of the trace classes S_p (1\u2264 p < \u221e )","volume":"50","author":"Tomczak-Jaegermann Nicole","year":"1974","unstructured":"Nicole Tomczak-Jaegermann. 1974. The moduli of smoothness and convexity and the Rademacher averages of the trace classes S_p (1\u2264 p < \u221e ). Studia Mathematica, 50, 2 (1974), 163\u2013182. http:\/\/eudml.org\/doc\/217886","journal-title":"Studia Mathematica"},{"key":"e_1_3_2_1_66_1","unstructured":"Ryota Tomioka and Taiji Suzuki. 2014. Spectral norm of random tensors. arXiv preprint arXiv:1407.1870 https:\/\/api.semanticscholar.org\/CorpusID:88513612"},{"key":"e_1_3_2_1_67_1","volume-title":"An Introduction to Matrix Concentration Inequalities","author":"Tropp J.A.","year":"1988","unstructured":"J.A. Tropp. 2015. An Introduction to Matrix Concentration Inequalities. Now Publishers. isbn:9781601988393 https:\/\/books.google.ch\/books?id=xN0WjwEACAAJ"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","unstructured":"Joel A Tropp. 2016. The expected norm of a sum of independent random matrices: An elementary approach. In High Dimensional Probability VII: The Cargese Volume. 173\u2013202. https:\/\/doi.org\/10.1007\/978-3-319-40519-3_8 10.1007\/978-3-319-40519-3_8","DOI":"10.1007\/978-3-319-40519-3_8"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1090\/tran"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-7005-6_4"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.000-2"},{"key":"e_1_3_2_1_73_1","volume-title":"Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science, 10, 1\u20132","author":"Woodruff David P","year":"2014","unstructured":"David P Woodruff. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science, 10, 1\u20132 (2014), 1\u2013157. https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679820"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","unstructured":"Zhixin Zhou and Yizhe Zhu. 2021. Sparse random tensors: Concentration regularization and applications. https:\/\/doi.org\/10.1214\/21-EJS1838 10.1214\/21-EJS1838","DOI":"10.1214\/21-EJS1838"}],"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.3718188","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:42:46Z","timestamp":1750693366000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718188"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":75,"alternative-id":["10.1145\/3717823.3718188","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718188","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"}}]}}