{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:26Z","timestamp":1781077646069,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","funder":[{"name":"NSF","award":["2238080, 2107079"],"award-info":[{"award-number":["2238080, 2107079"]}]},{"name":"ERC","award":["815464"],"award-info":[{"award-number":["815464"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718293","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1701-1709","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More"],"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":"Simons Institute for the Theory of Computing, Berkeley, USA"},{"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","unstructured":"K. Ahn D. Medarametla and A. Potechin. 2020. Graph matrices: norm bounds and applications. arXiv preprint arXiv:1604.03423."},{"key":"e_1_3_2_1_2_1","volume-title":"Proc. 2008 IEEE International Symposium on Information Theory.","author":"Amini A. A.","unstructured":"A. A. Amini and M. J. Wainwright. 2008. High-dimensional analysis of semidefinite relaxations for sparse principal components. In Proc. 2008 IEEE International Symposium on Information Theory."},{"key":"e_1_3_2_1_3_1","volume-title":"Proc. 40th International Conference on Machine Learning (ICML).","author":"Asi H.","unstructured":"H. Asi, J. R. Ullman, and L. Zakynthinou. 2023. From Robustness to Privacy and Back. In Proc. 40th International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_1_4_1","volume-title":"Proc. 44th Annual ACM Symposium on Theory of Computing (STOC).","author":"Barak B.","unstructured":"B. Barak, F. GSL Brandao, A. W. Harrow, J. Kelner, D. Steurer, and Y. Zhou. 2012. Hypercontractivity, sum-of-squares proofs, and their applications. In Proc. 44th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_5_1","volume-title":"Proc. 46th Annual ACM Symposium on Theory of Computing (STOC).","author":"Barak B.","unstructured":"B. Barak, J. Kelner, and D. Steurer. 2014. Rounding sum-of-squares relaxations. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_6_1","volume-title":"Conference on Learning Theory. 417\u2013445","author":"Barak B.","unstructured":"B. Barak and A. Moitra. 2016. Noisy tensor completion via the sumofsquares hierarchy. In Conference on Learning Theory. 417\u2013445."},{"key":"e_1_3_2_1_7_1","volume-title":"Proc. 36th Annual Conference on Learning Theory (COLT).","author":"Brown G.","unstructured":"G. Brown, S. B. Hopkins, and A. D. Smith. 2023. Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions. In Proc. 36th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"E. J. Candes and T. Tao. 2005. Decoding by linear programming. IEEE transactions on information theory.","DOI":"10.1109\/TIT.2005.858979"},{"key":"e_1_3_2_1_9_1","volume-title":"Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Canonne C. L.","unstructured":"C. L. Canonne, S. B. Hopkins, J. Li, A. Liu, and S. Narayanan. 2023. The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination. In Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_10_1","volume-title":"Proc. 29th Annual Conference on Learning Theory (COLT).","author":"Chan S. O.","unstructured":"S. O. Chan, D. Papailliopoulos, and A. Rubinstein. 2016. On the approximability of sparse PCA. In Proc. 29th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_11_1","volume-title":"Proc. 35th Annual Conference on Learning Theory (COLT).","author":"Chen H.","year":"2022","unstructured":"H. Chen and T. d\u2019Orsi. 2022. On the well-spread property and its relation to linear regression. In Proc. 35th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1607"},{"key":"e_1_3_2_1_13_1","article-title":"Optimal Solutions for Sparse Principal Component Analysis","author":"Aspremont A.","year":"2008","unstructured":"A. d\u2019Aspremont, F. Bach, and L. El Ghaoui. 2008. Optimal Solutions for Sparse Principal Component Analysis.. Journal of Machine Learning Research.","journal-title":"Journal of Machine Learning Research."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"L. Demanet and P. Hand. 2014. Scaling law for recovering the sparsest element in a subspace. Information and Inference: A Journal of the IMA.","DOI":"10.1093\/imaiai\/iau007"},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. 2014 IEEE International Symposium on Information Theory.","author":"Deshpande Y.","unstructured":"Y. Deshpande and A. Montanari. 2014. Information-theoretically optimal sparse PCA. In Proc. 2014 IEEE International Symposium on Information Theory."},{"key":"e_1_3_2_1_16_1","article-title":"Sparse PCA via covariance thresholding","author":"Deshpande Y.","year":"2016","unstructured":"Y. Deshpande and A. Montanari. 2016. Sparse PCA via covariance thresholding. Journal of Machine Learning Research.","journal-title":"Journal of Machine Learning Research."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas S. B. Hopkins A. Pensia and S. Tiegel. 2024. SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications. arXiv preprint arXiv:2410.21194.","DOI":"10.1145\/3717823.3718183"},{"key":"e_1_3_2_1_18_1","volume-title":"Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. 2016. Robust Estimators in High Dimensions without the Computational Intractability. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_19_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_20_1","volume-title":"Proc. 35th Annual Conference on Learning Theory (COLT).","author":"Diakonikolas I.","unstructured":"I. Diakonikolas and D. M. Kane. 2022. Non-gaussian component analysis via lattice basis reduction. In Proc. 35th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_21_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_22_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_23_1","unstructured":"I. Diakonikolas D. M. Kane and A. Pensia. 2020. Outlier Robust Mean Estimation with Subgaussian Rates via Stability. In Advances in Neural Information Processing Systems 33 (NeurIPS)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_25_1","volume-title":"Proc. 30th Annual Symposium on Discrete Algorithms (SODA).","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, W. Kong, and A. Stewart. 2019. Efficient Algorithms and Lower Bounds for Robust Linear Regression. In Proc. 30th Annual Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Y. Ding D. Kunisky A. Wein and A. Bandeira. 2024. Subexponentialtime algorithms for sparse PCA. Foundations of Computational Mathematics.","DOI":"10.1007\/s10208-023-09603-0"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Orsi T.","unstructured":"T. d\u2019Orsi, P. K. Kothari, G. Novikov, and D. Steurer. 2020. Sparse PCA: algorithms, adversarial perturbations and certificates. In Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_29_1","volume-title":"Proc. 36th Annual Conference on Learning Theory (COLT).","author":"Duchi J. C.","unstructured":"J. C. Duchi, R. Kuditipudi, and S. Haque. 2023. A Pretty Fast Algorithm for Adaptive Private Mean Estimation. In Proc. 36th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_30_1","volume-title":"Proc. 41st Annual ACM Symposium on Theory of Computing (STOC).","author":"Dwork C.","unstructured":"C. Dwork and J. Lei. 2009. Differential privacy and robust statistics. In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345462"},{"key":"e_1_3_2_1_32_1","unstructured":"R. Ge and T. Ma. 2015. Decomposing Overcomplete 3rd Order Tensors using SumofSquares Algorithms. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)."},{"key":"e_1_3_2_1_33_1","unstructured":"K. Georgiev and S. B. Hopkins. 2022. Privacy Induces Robustness: InformationComputation Gaps and Sparse Mean Estimation. In Advances in Neural Information Processing Systems 35 (NeurIPS)."},{"key":"e_1_3_2_1_34_1","volume-title":"Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Guruswami V.","unstructured":"V. Guruswami, J.-T. Hsieh, and P. Raghavendra. 2024. Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the \u221a n Dimension Threshold. In Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"V. Guruswami J. Lee and A. Wigderson. 2008. Euclidean Sections of \u2113 _1^N with Sublinear Randomness and Error-Correction over the Reals. In Approximation Randomization and Combinatorial Optimization.","DOI":"10.1007\/978-3-540-85363-3_35"},{"key":"e_1_3_2_1_36_1","volume-title":"Proc. 33rd Annual Conference on Learning Theory (COLT).","author":"Holtzman G.","unstructured":"G. Holtzman, A. Soffer, and D. Vilenchik. 2020. A greedy anytime algorithm for sparse PCA. In Proc. 33rd Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_37_1","volume-title":"Proc. 55th Annual ACM Symposium on Theory of Computing (STOC).","author":"Hopkins S. B.","unstructured":"S. B. Hopkins, G. Kamath, M. Majid, and S. Narayanan. 2023. Robustness Implies Privacy in Statistical Estimation. In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_38_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_39_1","volume-title":"Proc. 49th Annual ACM Symposium on Theory of Computing (STOC).","author":"Hopkins S. B.","unstructured":"S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. 2016. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proc. 49th Annual ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_40_1","volume-title":"Conference on Learning Theory. 956\u20131006","author":"Hopkins S. B.","unstructured":"S. B. Hopkins, J. Shi, and D. Steurer. 2015. Tensor principal component analysis via sumofsquare proofs. In Conference on Learning Theory. 956\u20131006."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2009.0121"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"B. S. Kashin. 1977. Diameters of some finite-dimensional sets and classes of smooth functions. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya.","DOI":"10.1070\/IM1977v011n02ABEH001719"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"B. S. Kashin and V. N Temlyakov. 2007. A remark on compressed sensing. Mathematical notes.","DOI":"10.1134\/S0001434607110193"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_46_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_47_1","volume-title":"Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Lai K. A.","unstructured":"K. A. Lai, A. B. Rao, and S. Vempala. 2016. Agnostic Estimation of Mean and Covariance. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_48_1","unstructured":"J. Lindenstrauss. 1977. The dimension of almost spherical sections of convex bodies. S\u00e9minaire Maurey-Schwartz 1\u201313."},{"key":"e_1_3_2_1_49_1","unstructured":"C. Mao and A. S. Wein. 2021. Optimal spectral recovery of a planted vector in a subspace. arXiv preprint arXiv:2105.15081."},{"key":"e_1_3_2_1_50_1","volume-title":"Conference on Learning Theory. 3979\u20134027","author":"Narayanan S.","year":"2022","unstructured":"S. Narayanan. 2022. Private high-dimensional hypothesis testing. In Conference on Learning Theory. 3979\u20134027."},{"key":"e_1_3_2_1_51_1","unstructured":"Q. Qu J. Sun and J. Wright. 2014. Finding a sparse vector in a subspace: Linear sparsity using alternating directions. Advances in Neural Information Processing Systems 27 (NeurIPS)."},{"key":"e_1_3_2_1_52_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing.","author":"Raghavendra P.","unstructured":"P. Raghavendra, S. Rao, and T. Schramm. 2017. Strongly refuting random csps below the spectral threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing."},{"key":"e_1_3_2_1_53_1","volume-title":"Proc. 25th Annual Conference on Learning Theory (COLT).","author":"Spielman D. A.","unstructured":"D. A. Spielman, H. Wang, and J. Wright. 2012. Exact Recovery of Sparsely-Used Dictionaries. In Proc. 25th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_54_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_55_1","volume-title":"Proc. 35th Annual Conference on Learning Theory (COLT).","author":"Zadik I.","unstructured":"I. Zadik, M. J. Song, A. S. Wein, and J. Bruna. 2022. Lattice-based methods surpass sum-of-squares in clustering. In Proc. 35th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1198\/106186006X113430"}],"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.3718293","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:48:58Z","timestamp":1750693738000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":56,"alternative-id":["10.1145\/3717823.3718293","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718293","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"}}]}}