{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:16:10Z","timestamp":1781259370057,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["2238080, 2107079"],"award-info":[{"award-number":["2238080, 2107079"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718183","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1689-1700","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5486-1856","authenticated-orcid":false,"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6519-8079","authenticated-orcid":false,"given":"Samuel B.","family":"Hopkins","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3509-1224","authenticated-orcid":false,"given":"Ankit","family":"Pensia","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9719-0036","authenticated-orcid":false,"given":"Stefan","family":"Tiegel","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proc. 18th Annual Conference on Learning Theory (COLT).","author":"Achlioptas D.","unstructured":"D. Achlioptas and F. McSherry. 2005. On spectral learning of mixtures of distributions. In Proc. 18th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"A. Bakshi P. Kothari G. Rajendran M. Tulsiani and A. Vijayaraghavan. 2024. Efficient Certificates of Anti-Concentration Beyond Gaussians. arXiv preprint arXiv:2405.15084.","DOI":"10.1109\/FOCS61266.2024.00065"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451001"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_3_2_1_5_1","unstructured":"B. Barak and D. Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. 1 (2016) http:\/\/www.sumofsquares.org\/public\/index.html"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"e_1_3_2_1_7_1","volume-title":"Proc. 34th Annual Conference on Learning Theory (COLT).","author":"Brennan M.","unstructured":"M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T. Schramm. 2021. Statistical query algorithms and low-degree tests are almost equivalent. In Proc. 34th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_3_2_1_9_1","volume-title":"SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications. arXiv, 2410.21194","author":"Diakonikolas Ilias","year":"2024","unstructured":"Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, and Stefan Tiegel. 2024. SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications. arXiv, 2410.21194 (2024)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.85"},{"key":"e_1_3_2_1_11_1","volume-title":"Proc. 34th International Conference on Machine Learning (ICML).","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. 2017. Being Robust (in High Dimensions) Can Be Practical. In Proc. 34th International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas and D. M. Kane. 2023. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press.","DOI":"10.1017\/9781108943161"},{"key":"e_1_3_2_1_13_1","unstructured":"I. Diakonikolas D. M. Kane S. Karmalkar A. Pensia and T. Pittas. 2022. List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering. In Advances in Neural Information Processing Systems 35 (NeurIPS)."},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. 35th Annual Conference on Learning Theory (COLT).","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, D. M. Kane, S. Karmalkar, A. Pensia, and T. Pittas. 2022. Robust Sparse Mean Estimation via Sum of Squares. In Proc. 35th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_16_1","volume-title":"Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, S. Karmalkar, S. Pang, and A. Potechin. 2024. Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis. In Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"N. Fleming P. Kothari and T. Pitassi. 2019. Semialgebraic Proofs and Efficient Algorithm Design. Found. Trends Theor. Comput. Sci..","DOI":"10.1561\/9781680836370"},{"key":"e_1_3_2_1_19_1","unstructured":"A. Gollakota A. R. Klivans K. Stavropoulos and A. Vasilyan. 2023. Tester-Learners for Halfspaces: Universal Algorithms. In Advances in Neural Information Processing Systems 36 (NeurIPS)."},{"key":"e_1_3_2_1_20_1","volume-title":"\u201c Workshop on Computational Efficiency and High-Dimensional Robust Statistics","author":"Hopkins S.","unstructured":"S. Hopkins. 2018. SoS Method for Robust Estimation of Higher Moments. \u201c Workshop on Computational Efficiency and High-Dimensional Robust Statistics \u201d at TTI Chicago. http:\/\/www.iliasdiakonikolas.org\/tti-robust\/Hopkins.pdf See Slide 21"},{"key":"e_1_3_2_1_21_1","volume-title":"Proc. 50th Annual ACM Symposium on Theory of Computing (STOC).","author":"Hopkins S. B.","unstructured":"S. B. Hopkins and J. Li. 2018. Mixture Models, Robustness, and Sum of Squares Proofs. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_22_1","volume-title":"Proc. 32nd Annual Conference on Learning Theory (COLT).","author":"Hopkins S. B.","unstructured":"S. B. Hopkins and J. Li. 2019. How Hard Is Robust Mean Estimation? In Proc. 32nd Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"P. J. Huber and E. M. Ronchetti. 2009. Robust Statistics. John Wiley & Sons.","DOI":"10.1002\/9780470434697"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"C. Josz and D. Henrion. 2016. Strong duality in Lasserre\u2019s hierarchy for polynomial optimization. Optimization Letters.","DOI":"10.1007\/s11590-015-0868-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"J. Kahane. 1960. Propri\u00e9t\u00e9s locales des fonctions \u00e0 s\u00e9ries de Fourier al\u00e9atoires. Studia Mathematica.","DOI":"10.4064\/sm-19-1-1-25"},{"key":"e_1_3_2_1_26_1","volume-title":"Proc. 31st Annual Conference on Learning Theory (COLT).","author":"Klivans A.","unstructured":"A. Klivans, P. K. Kothari, and R. Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Proc. 31st Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_27_1","volume-title":"Recent Progress in Algorithmic Robust Statistics via the Sum-of-Squares Method. \u2018\u2019Learning and Testing in High Dimensions","author":"Kothari P.","year":"1883","unstructured":"P. Kothari. 2020. Recent Progress in Algorithmic Robust Statistics via the Sum-of-Squares Method. \u2018\u2019Learning and Testing in High Dimensions\u201d at Simons Institute. https:\/\/www.youtube.com\/watch?v=xKoMFCQojCk&t=1883s"},{"key":"e_1_3_2_1_28_1","unstructured":"P. K. Kothari P. Manohar and B. H. Zhang. 2022. Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. 638\u2013667."},{"key":"e_1_3_2_1_29_1","volume-title":"Proc. 35th Annual Conference on Learning Theory (COLT).","author":"Kothari P. K.","unstructured":"P. K. Kothari, P. Manurangsi, and A. Velingker. 2022. Private Robust Estimation by Stabilizing Convex Relaxations. In Proc. 35th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_30_1","unstructured":"P. K. Kothari and J. Steinhardt. 2017. Better Agnostic Clustering Via Relaxed Tensor Norms. CoRR abs\/1711.07465 (2017) arXiv:1711.07465. arxiv:1711.07465"},{"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","unstructured":"P. K Kothari and D. Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"M. Laurent. 2009. Sums of Squares Moment Matrices and Optimization Over Polynomials.","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","unstructured":"M. Ledoux and M. Talagrand. 1991. Probability in Banach Spaces. Springer Berlin Heidelberg Berlin Heidelberg. isbn:978-3-642-20211-7 978-3-642-20212-4 https:\/\/doi.org\/10.1007\/978-3-642-20212-4 10.1007\/978-3-642-20212-4","DOI":"10.1007\/978-3-642-20212-4"},{"key":"e_1_3_2_1_36_1","volume-title":"\u2018\u2019Robust and High-Dimensional Statistics","author":"Mixture Models J. Li.","unstructured":"J. Li. 2018. Mixture Models, Robustness, and Sum of Squares Proofs. \u2018\u2019Robust and High-Dimensional Statistics\u201d at Simons Institute. https:\/\/www.youtube.com\/watch?v=pyzkMCc78lM&t=2164"},{"key":"e_1_3_2_1_37_1","volume-title":"Proc. 42nd Annual ACM Symposium on Theory of Computing (STOC).","author":"Raghavendra P.","unstructured":"P. Raghavendra and D. Steurer. 2010. Graph expansion and the unique games conjecture. In Proc. 42nd Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_38_1","volume-title":"Proc. 9th Innovations in Theoretical Computer Science Conference (ITCS).","author":"Steinhardt J.","unstructured":"J. Steinhardt, M. Charikar, and G. Valiant. 2018. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. In Proc. 9th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","unstructured":"M. Talagrand. 2021. Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems. https:\/\/doi.org\/10.1007\/978-3-030-82595-9 10.1007\/978-3-030-82595-9","DOI":"10.1007\/978-3-030-82595-9"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"e_1_3_2_1_41_1","volume-title":"High-Dimensional Statistics: A Non-Asymptotic Viewpoint","author":"Wainwright M. J.","unstructured":"M. J. Wainwright. 2019. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press. isbn:978-1-108-62777-1 978-1-108-49802-9"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3718183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:42:28Z","timestamp":1750693348000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":41,"alternative-id":["10.1145\/3717823.3718183","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718183","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"}}]}}