{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:13:23Z","timestamp":1781259203157,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":46,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520012","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1248-1261","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Clustering mixtures with almost optimal separation in polynomial time"],"prefix":"10.1145","author":[{"given":"Allen","family":"Liu","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.83"},{"key":"e_1_3_2_1_2_1","unstructured":"Jayadev Acharya Ashkan Jafarpour Alon Orlitsky and Ananda Theertha Suresh. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. arXiv preprint arXiv:1402.4746.  Jayadev Acharya Ashkan Jafarpour Alon Orlitsky and Ananda Theertha Suresh. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. arXiv preprint arXiv:1402.4746."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"e_1_3_2_1_4_1","volume-title":"Conference on Learning Theory. 1135\u20131164","author":"Anderson Joseph","year":"2014","unstructured":"Joseph Anderson , Mikhail Belkin , Navin Goyal , Luis Rademacher , and James Voss . 2014 . The more, the merrier: the blessing of dimensionality for learning large Gaussian mixtures . In Conference on Learning Theory. 1135\u20131164 . Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James Voss. 2014. The more, the merrier: the blessing of dimensionality for learning large Gaussian mixtures. In Conference on Learning Theory. 1135\u20131164."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000512"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems. 3416\u20133425","author":"Ashtiani Hassan","year":"2018","unstructured":"Hassan Ashtiani , Shai Ben-David , Nicholas JA Harvey , Christopher Liaw , Abbas Mehrabian , and Yaniv Plan . 2018 . Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes . In Proceedings of the 32nd International Conference on Neural Information Processing Systems. 3416\u20133425 . Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. 2018. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. In Proceedings of the 32nd International Conference on Neural Information Processing Systems. 3416\u20133425."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090818X"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"e_1_3_2_1_9_1","unstructured":"Aditya Bhaskara Ananda Suresh and Morteza Zadimoghaddam. 2015. Sparse solutions to nonnegative linear systems and applications. In Artificial Intelligence and Statistics. 83\u201392.  Aditya Bhaskara Ananda Suresh and Morteza Zadimoghaddam. 2015. Sparse solutions to nonnegative linear systems and applications. In Artificial Intelligence and Statistics. 83\u201392."},{"key":"e_1_3_2_1_10_1","unstructured":"Matthew Brennan Guy Bresler Samuel B Hopkins Jerry Li and Tselil Schramm. 2020. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.06107.  Matthew Brennan Guy Bresler Samuel B Hopkins Jerry Li and Tselil Schramm. 2020. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.06107."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591848"},{"key":"e_1_3_2_1_12_1","unstructured":"Siu-On Chan Ilias Diakonikolas Rocco A Servedio and Xiaorui Sun. 2014. Near-optimal density estimation in near-linear time using variable-width histograms. arXiv preprint arXiv:1411.0169.  Siu-On Chan Ilias Diakonikolas Rocco A Servedio and Xiaorui Sun. 2014. Near-optimal density estimation in near-linear time using variable-width histograms. arXiv preprint arXiv:1411.0169."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-021-00558-4"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"e_1_3_2_1_15_1","first-page":"203","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical Gaussians","volume":"8","author":"Dasgupta Sanjoy","year":"2007","unstructured":"Sanjoy Dasgupta and Leonard J Schulman . 2007 . A probabilistic analysis of EM for mixtures of separated, spherical Gaussians . Journal of Machine Learning Research , 8 (2007), 203 \u2013 226 . Sanjoy Dasgupta and Leonard J Schulman. 2007. A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. Journal of Machine Learning Research, 8 (2007), 203\u2013226.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_16_1","volume-title":"Conference on Learning Theory. 1183\u20131213","author":"Daskalakis Constantinos","year":"2014","unstructured":"Constantinos Daskalakis and Gautam Kamath . 2014 . Faster and sample near-optimal algorithms for proper learning mixtures of gaussians . In Conference on Learning Theory. 1183\u20131213 . Constantinos Daskalakis and Gautam Kamath. 2014. Faster and sample near-optimal algorithms for proper learning mixtures of gaussians. In Conference on Learning Theory. 1183\u20131213."},{"key":"e_1_3_2_1_17_1","volume-title":"Conference on Learning Theory. 704\u2013710","author":"Daskalakis Constantinos","year":"2017","unstructured":"Constantinos Daskalakis , Christos Tzamos , and Manolis Zampetakis . 2017 . Ten steps of EM suffice for mixtures of two Gaussians . In Conference on Learning Theory. 704\u2013710 . Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. 2017. Ten steps of EM suffice for mixtures of two Gaussians. In Conference on Learning Theory. 704\u2013710."},{"key":"e_1_3_2_1_18_1","volume-title":"Combinatorial methods in density estimation","author":"Devroye Luc","unstructured":"Luc Devroye and G\u00e1bor Lugosi . 2001. Combinatorial methods in density estimation . Springer Science & Business Media . Luc Devroye and G\u00e1bor Lugosi. 2001. Combinatorial methods in density estimation. Springer Science & Business Media."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00026"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188758"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/060670705"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.58"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746579"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory. 1683\u20131722","author":"Hopkins Samuel B","year":"2019","unstructured":"Samuel B Hopkins , Tselil Schramm , and Jonathan Shi . 2019 . A robust spectral algorithm for overcomplete tensor decomposition . In Conference on Learning Theory. 1683\u20131722 . Samuel B Hopkins, Tselil Schramm, and Jonathan Shi. 2019. A robust spectral algorithm for overcomplete tensor decomposition. In Conference on Learning Theory. 1683\u20131722."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422439"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806765"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_1_33_1","unstructured":"Jerry Li Allen Liu and Ankur Moitra. 2021. Sparsification for Sums of Exponentials and its Algorithmic Applications. arXiv preprint arXiv:2106.02774.  Jerry Li Allen Liu and Ankur Moitra. 2021. Sparsification for Sums of Exponentials and its Algorithmic Applications. arXiv preprint arXiv:2106.02774."},{"key":"e_1_3_2_1_34_1","volume-title":"Conference on Learning Theory. 1302\u20131382","author":"Li Jerry","year":"2017","unstructured":"Jerry Li and Ludwig Schmidt . 2017 . Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities . In Conference on Learning Theory. 1302\u20131382 . Jerry Li and Ludwig Schmidt. 2017. Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities. In Conference on Learning Theory. 1302\u20131382."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.54"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iax001"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1894.0003"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055417"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Oded Regev and Aravindan Vijayaraghavan. 2017. On Learning Mixtures of Well-Separated Gaussians. arxiv:1710.11592.  Oded Regev and Aravindan Vijayaraghavan. 2017. On Learning Mixtures of Well-Separated Gaussians. arxiv:1710.11592.","DOI":"10.1109\/FOCS.2017.17"},{"key":"e_1_3_2_1_41_1","volume-title":"Conference on Learning Theory. 1760\u20131793","author":"Schramm Tselil","year":"2017","unstructured":"Tselil Schramm and David Steurer . 2017 . Fast and robust tensor decomposition with applications to dictionary learning . In Conference on Learning Theory. 1760\u20131793 . Tselil Schramm and David Steurer. 2017. Fast and robust tensor decomposition with applications to dictionary learning. In Conference on Learning Theory. 1760\u20131793."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.24"},{"key":"e_1_3_2_1_43_1","unstructured":"Yin Tat Lee and Santosh S Vempala. 2018. The Kannan-Lov\u00e1sz-Simonovits Conjecture. arXiv e-prints arXiv\u20131807.  Yin Tat Lee and Santosh S Vempala. 2018. The Kannan-Lov\u00e1sz-Simonovits Conjecture. arXiv e-prints arXiv\u20131807."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"},{"key":"e_1_3_2_1_45_1","first-page":"95","article-title":"On the convergence properties of the EM algorithm","author":"Jeff Wu CF","year":"1983","unstructured":"CF Jeff Wu . 1983 . On the convergence properties of the EM algorithm . The Annals of statistics , 95 \u2013 103 . CF Jeff Wu. 1983. On the convergence properties of the EM algorithm. The Annals of statistics, 95\u2013103.","journal-title":"The Annals of statistics"},{"key":"e_1_3_2_1_46_1","unstructured":"Ji Xu Daniel Hsu and Arian Maleki. 2016. Global analysis of expectation maximization for mixtures of two gaussians. arXiv preprint arXiv:1608.07630.  Ji Xu Daniel Hsu and Arian Maleki. 2016. Global analysis of expectation maximization for mixtures of two gaussians. arXiv preprint arXiv:1608.07630."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3520012","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":46,"alternative-id":["10.1145\/3519935.3520012","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520012","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"}}]}}