{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:54Z","timestamp":1750309314727,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF (National Science Foundation)","award":["CCF-1652491, ECCS-2216970, CCF-2008688, CCF-2047288"],"award-info":[{"award-number":["CCF-1652491, ECCS-2216970, CCF-2008688, CCF-2047288"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649765","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"375-386","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5505-3140","authenticated-orcid":false,"given":"Aditya","family":"Bhaskara","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5488-8725","authenticated-orcid":false,"given":"Eric","family":"Evert","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-1947-3975","authenticated-orcid":false,"given":"Vaidehi","family":"Srinivas","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9734-3779","authenticated-orcid":false,"given":"Aravindan","family":"Vijayaraghavan","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Graph Matrices: Norm Bounds and Applications.. arXiv: Combinatorics, https:\/\/api.semanticscholar.org\/CorpusID:211252816","author":"Ahn Kwangjun","year":"2016","unstructured":"Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. 2016. Graph Matrices: Norm Bounds and Applications.. arXiv: Combinatorics, https:\/\/api.semanticscholar.org\/CorpusID:211252816"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24486-0_2"},{"key":"e_1_3_2_1_3_1","volume-title":"COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, Shie Mannor, Nathan Srebro, and Robert C. Williamson (Eds.) (JMLR Proceedings","volume":"33","author":"Anandkumar Animashree","unstructured":"Animashree Anandkumar, Daniel J. Hsu, and Sham M. Kakade. 2012. A Method of Moments for Mixture Models and Hidden Markov Models. In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, Shie Mannor, Nathan Srebro, and Robert C. Williamson (Eds.) (JMLR Proceedings, Vol. 23). JMLR.org, 33.1\u201333.34. http:\/\/proceedings.mlr.press\/v23\/anandkumar12\/anandkumar12.pdf"},{"key":"e_1_3_2_1_4_1","unstructured":"Nima Anari Constantinos Daskalakis Wolfgang Maass Christos Papadimitriou Amin Saberi and Santosh Vempala. 2018. Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the Neural Information Processing Systems (NeurIPS).","author":"Awasthi Pranjal","year":"2021","unstructured":"Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan. 2021. Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations. In Proceedings of the Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.016"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00094"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055488"},{"key":"e_1_3_2_1_9_1","volume-title":"Smoothed Analysis of Tensor Decompositions. In Symposium on the Theory of Computing (STOC).","author":"Bhaskara Aditya","year":"2014","unstructured":"Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan. 2014. Smoothed Analysis of Tensor Decompositions. In Symposium on the Theory of Computing (STOC)."},{"key":"e_1_3_2_1_10_1","volume-title":"Conference on Learning Theory.","author":"Bhaskara Aditya","year":"2014","unstructured":"Aditya Bhaskara, Moses Charikar, and Aravindan Vijayaraghavan. 2014. Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. Conference on Learning Theory."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00043"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00087"},{"volume-title":"Learning Mixtures of Gaussians in High Dimensions. In Symposium on Theory of Computing.","author":"Ge Rong","key":"e_1_3_2_1_13_1","unstructured":"Rong Ge, Qingqing Huang, and Sham M. Kakade. 2015. Learning Mixtures of Gaussians in High Dimensions. In Symposium on Theory of Computing."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591875"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591875"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.95"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.66"},{"key":"e_1_3_2_1_18_1","article-title":"Volumetric spanners: an efficient exploration basis for learning","author":"Hazan Elad","year":"2016","unstructured":"Elad Hazan and Zohar Karnin. 2016. Volumetric spanners: an efficient exploration basis for learning. Journal of Machine Learning Research.","journal-title":"Journal of Machine Learning Research."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00079"},{"key":"e_1_3_2_1_20_1","unstructured":"J. Lindenstrauss and L. Tzafriri. 2013. Classical Banach Spaces I: Sequence Spaces. Springer Berlin Heidelberg."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316357"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Goutham Rajendran and Madhur Tulsiani. [n. d.]. Concentration of polynomial random matrices via Efron-Stein inequalities. 3614\u20133653. https:\/\/doi.org\/10.1137\/1.9781611977554.ch138 arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977554.ch138. 10.1137\/1.9781611977554.ch138","DOI":"10.1137\/1.9781611977554.ch138"},{"volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Roughgarden Tim","key":"e_1_3_2_1_23_1","unstructured":"Tim Roughgarden. 2020. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.01.010"},{"key":"e_1_3_2_1_25_1","volume-title":"Training Input-Output Recurrent Neural Networks through Spectral Methods. CoRR, abs\/1603.00954","author":"Sedghi Hanie","year":"2016","unstructured":"Hanie Sedghi and Anima Anandkumar. 2016. Training Input-Output Recurrent Neural Networks through Spectral Methods. CoRR, abs\/1603.00954 (2016), arXiv:1603.00954. arxiv:1603.00954"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"N. D. Sidiropoulos L. De Lathauwer X. Fu K. Huang E. E. Papalexakis and C. Faloutsos. 2017. Tensor Decomposition for Signal Processing and Machine Learning. 65 13 (2017) July 3551\u20133582.","DOI":"10.1109\/TSP.2017.2690524"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627708"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.3150\/20-BEJ1218"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Van Vu. 2017. Anti-concentration Inequalities for Polynomials. 801\u2013810. isbn:978-3-319-44478-9 https:\/\/doi.org\/10.1007\/978-3-319-44479-6_32 10.1007\/978-3-319-44479-6_32","DOI":"10.1007\/978-3-319-44479-6_32"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649765","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649765","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649765"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":30,"alternative-id":["10.1145\/3618260.3649765","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649765","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}