{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:08Z","timestamp":1750308428568,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"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.3520006","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1276-1283","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["List-decodable covariance estimation"],"prefix":"10.1145","author":[{"given":"Misha","family":"Ivkov","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Vempala","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi , Ilias Diakonikolas , He Jia , Daniel M. Kane , Pravesh K. Kothari , and Santosh S . Vempala . 2020 . Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR , abs\/2012.02119 (2020), arXiv:2012.02119. arxiv:2012.02119 Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR, abs\/2012.02119 (2020), arXiv:2012.02119. arxiv:2012.02119"},{"unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139. Ainesh Bakshi and Pravesh Kothari. 2020. List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139.","key":"e_1_3_2_1_2_1"},{"doi-asserted-by":"crossref","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures.","key":"e_1_3_2_1_3_1","DOI":"10.1109\/FOCS46700.2020.00023"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1137\/1.9781611976465.78"},{"doi-asserted-by":"crossref","unstructured":"Maria-Florina Balcan Avrim Blum and Santosh Vempala. 2008. A discriminative framework for clustering via similarity functions. In STOC. ACM 671\u2013680. Maria-Florina Balcan Avrim Blum and Santosh Vempala. 2008. A discriminative framework for clustering via similarity functions. In STOC. ACM 671\u2013680.","key":"e_1_3_2_1_5_1","DOI":"10.1145\/1374376.1374474"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1007\/978-1-4612-0701-6"},{"doi-asserted-by":"crossref","unstructured":"Moses Charikar Jacob Steinhardt and Gregory Valiant. 2017. Learning from untrusted data. In STOC. ACM 47\u201360. Moses Charikar Jacob Steinhardt and Gregory Valiant. 2017. Learning from untrusted data. In STOC. ACM 47\u201360.","key":"e_1_3_2_1_7_1","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_3_2_1_8_1","volume-title":"Fast Mean Estimation with Sub-Gaussian Rates. In Conference on Learning Theory, COLT 2019","volume":"806","author":"Cherapanamjeri Yeshwanth","year":"2019","unstructured":"Yeshwanth Cherapanamjeri , Nicolas Flammarion , and Peter L. Bartlett . 2019 . Fast Mean Estimation with Sub-Gaussian Rates. In Conference on Learning Theory, COLT 2019 , 25-28 June 2019 , Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research , Vol. 99). PMLR, 786\u2013 806 . http:\/\/proceedings.mlr.press\/v99\/cherapanamjeri19b.html Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett. 2019. Fast Mean Estimation with Sub-Gaussian Rates. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, 786\u2013806. http:\/\/proceedings.mlr.press\/v99\/cherapanamjeri19b.html"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/3357713.3384329"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1109\/FOCS46700.2020.00022"},{"unstructured":"Ilias Diakonikolas Samuel Hopkins Daniel Kane and Sushrut Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. Personal Communication. Ilias Diakonikolas Samuel Hopkins Daniel Kane and Sushrut Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. Personal Communication.","key":"e_1_3_2_1_11_1"},{"volume-title":"Robust Estimators in High Dimensions without the Computational Intractability","author":"Diakonikolas Ilias","unstructured":"Ilias Diakonikolas , Gautam Kamath , Daniel M. Kane , Jerry Li , Ankur Moitra , and Alistair Stewart . 2016. Robust Estimators in High Dimensions without the Computational Intractability . In FOCS. IEEE Computer Society , 655\u2013664. Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. 2016. Robust Estimators in High Dimensions without the Computational Intractability. In FOCS. IEEE Computer Society, 655\u2013664.","key":"e_1_3_2_1_12_1"},{"key":"e_1_3_2_1_13_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas , Daniel Kane , and Daniel Kongsgaard . 2020 . List-Decodable Mean Estimation via Iterative Multi-Filtering . In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/6933b5648c59d618bbb30986c84080fe-Abstract.html Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard. 2020. List-Decodable Mean Estimation via Iterative Multi-Filtering. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/6933b5648c59d618bbb30986c84080fe-Abstract.html"},{"key":"e_1_3_2_1_14_1","volume-title":"List-Decodable Mean Estimation in Nearly-PCA Time. CoRR, abs\/2011.09973","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas , Daniel M. Kane , Daniel Kongsgaard , Jerry Li , and Kevin Tian . 2020. List-Decodable Mean Estimation in Nearly-PCA Time. CoRR, abs\/2011.09973 ( 2020 ), arXiv:2011.09973. arxiv:2011.09973 Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian. 2020. List-Decodable Mean Estimation in Nearly-PCA Time. CoRR, abs\/2011.09973 (2020), arXiv:2011.09973. arxiv:2011.09973"},{"key":"e_1_3_2_1_15_1","volume-title":"Statistical Query Lower Bounds for List-Decodable Linear Regression. CoRR, abs\/2106.09689","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas , Daniel M. Kane , Ankit Pensia , Thanasis Pittas , and Alistair Stewart . 2021. Statistical Query Lower Bounds for List-Decodable Linear Regression. CoRR, abs\/2106.09689 ( 2021 ), arXiv:2106.09689. arxiv:2106.09689 Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas, and Alistair Stewart. 2021. Statistical Query Lower Bounds for List-Decodable Linear Regression. CoRR, abs\/2106.09689 (2021), arXiv:2106.09689. arxiv:2106.09689"},{"volume-title":"Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures","author":"Diakonikolas Ilias","unstructured":"Ilias Diakonikolas , Daniel M. Kane , and Alistair Stewart . 2017. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures . In FOCS. IEEE Computer Society , 73\u201384. Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. In FOCS. IEEE Computer Society, 73\u201384.","key":"e_1_3_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1145\/3188745.3188758"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1109\/FOCS46700.2020.00099"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1561\/0400000086"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1214\/19-AOS1843"},{"key":"e_1_3_2_1_21_1","volume-title":"Hopkins and Jerry Li","author":"Sam","year":"2017","unstructured":"Sam B. Hopkins and Jerry Li . 2017 . Mixture Models, Robustness , and Sum of Squares Proofs . Sam B. Hopkins and Jerry Li. 2017. Mixture Models, Robustness, and Sum of Squares Proofs."},{"key":"e_1_3_2_1_22_1","volume-title":"List-decodable Linear Regression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Karmalkar Sushrut","year":"2019","unstructured":"Sushrut Karmalkar , Adam R. Klivans , and Pravesh Kothari . 2019 . List-decodable Linear Regression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 7423\u20137432. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/7f5fc754c7af0a6370c9bf91314e79f4-Abstract.html Sushrut Karmalkar, Adam R. Klivans, and Pravesh Kothari. 2019. List-decodable Linear Regression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 7423\u20137432. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/7f5fc754c7af0a6370c9bf91314e79f4-Abstract.html"},{"key":"e_1_3_2_1_23_1","volume-title":"Kothari and Jacob Steinhardt","author":"Pravesh","year":"2017","unstructured":"Pravesh K. Kothari and Jacob Steinhardt . 2017 . Better Agnostic Clustering via Relaxed Tensor Norms . Pravesh K. Kothari and Jacob Steinhardt. 2017. Better Agnostic Clustering via Relaxed Tensor Norms."},{"key":"e_1_3_2_1_24_1","volume-title":"Kothari and David Steurer","author":"Pravesh","year":"2017","unstructured":"Pravesh K. Kothari and David Steurer . 2017 . Outlier-robust moment-estimation via sum-of-squares. CoRR , abs\/1711.11581 (2017), arxiv:1711.11581. arxiv:1711.11581 Pravesh K. Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. CoRR, abs\/1711.11581 (2017), arxiv:1711.11581. arxiv:1711.11581"},{"volume-title":"Agnostic Estimation of Mean and Covariance","author":"Lai Kevin A.","unstructured":"Kevin A. Lai , Anup B. Rao , and Santosh Vempala . 2016. Agnostic Estimation of Mean and Covariance . In FOCS. IEEE Computer Society , 665\u2013674. Kevin A. Lai, Anup B. Rao, and Santosh Vempala. 2016. Agnostic Estimation of Mean and Covariance. In FOCS. IEEE Computer Society, 665\u2013674.","key":"e_1_3_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1145\/3406325.3451084"},{"doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra and Morris Yau. 2019. List Decodable Learning via Sum of Squares. In Manuscript. Prasad Raghavendra and Morris Yau. 2019. List Decodable Learning via Sum of Squares. In Manuscript.","key":"e_1_3_2_1_27_1","DOI":"10.1137\/1.9781611975994.10"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1137\/1.9781611975994.10"},{"unstructured":"Prasad Raghavendra and Morris Yau. 2020. List Decodable Subspace Recovery. arxiv:2002.03004. Prasad Raghavendra and Morris Yau. 2020. List Decodable Subspace Recovery. arxiv:2002.03004.","key":"e_1_3_2_1_29_1"},{"key":"e_1_3_2_1_30_1","volume-title":"List Decodable Subspace Recovery. In Conference on Learning Theory, COLT 2020","volume":"3226","author":"Raghavendra Prasad","year":"2020","unstructured":"Prasad Raghavendra and Morris Yau . 2020 . List Decodable Subspace Recovery. In Conference on Learning Theory, COLT 2020 , 9-12 July 2020, Virtual Event [Graz, Austria], Jacob D. Abernethy and Shivani Agarwal (Eds.) (Proceedings of Machine Learning Research , Vol. 125). PMLR, 3206\u2013 3226 . http:\/\/proceedings.mlr.press\/v125\/raghavendra20a.html Prasad Raghavendra and Morris Yau. 2020. List Decodable Subspace Recovery. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], Jacob D. Abernethy and Shivani Agarwal (Eds.) (Proceedings of Machine Learning Research, Vol. 125). PMLR, 3206\u20133226. http:\/\/proceedings.mlr.press\/v125\/raghavendra20a.html"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '22","name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy"},"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.3520006","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520006","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.3520006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":30,"alternative-id":["10.1145\/3519935.3520006","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520006","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"}}]}}