{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:00Z","timestamp":1781077800891,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["815464"],"award-info":[{"award-number":["815464"]}]},{"name":"NSF CAREER Award","award":["2047933, 2211971"],"award-info":[{"award-number":["2047933, 2211971"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585184","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1918-1926","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Algorithms Approaching the Threshold for Semi-random Planted Clique"],"prefix":"10.1145","author":[{"given":"Rares-Darius","family":"Buhai","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.3.CO;2-K"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00023"},{"key":"e_1_3_2_1_4_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"},{"key":"e_1_3_2_1_5_1","volume-title":"Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR, abs\/2005.02970","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi and Pravesh Kothari . 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR, abs\/2005.02970 ( 2020 ), arXiv:2005.02970. arxiv:2005.02970 Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR, abs\/2005.02970 (2020), arXiv:2005.02970. arxiv:2005.02970"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.78"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451001"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_9_1","volume-title":"A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem","author":"Barak Boaz","unstructured":"Boaz Barak , Samuel B. Hopkins , Jonathan A. Kelner , Pravesh Kothari , Ankur Moitra , and Aaron Potechin . 2016. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem . In FOCS. IEEE Computer Society , 428\u2013437. Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. 2016. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. In FOCS. IEEE Computer Society, 428\u2013437."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_11_1","unstructured":"Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. Lecture notes in preparation available on http:\/\/sumofsquares.org \t\t\t\t  Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. Lecture notes in preparation available on http:\/\/sumofsquares.org"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1034"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar Jacob Steinhardt and Gregory Valiant. 2017. Learning from untrusted data. In STOC. ACM 47\u201360. \t\t\t\t  Moses Charikar Jacob Steinhardt and Gregory Valiant. 2017. Learning from untrusted data. In STOC. ACM 47\u201360.","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_3_2_1_14_1","unstructured":"Yunzi Ding Dmitriy Kunisky Alexander S Wein and Afonso S Bandeira. 2019. Subexponential-time algorithms for sparse PCA. arXiv preprint arXiv:1907.11635. \t\t\t\t  Yunzi Ding Dmitriy Kunisky Alexander S Wein and Afonso S Bandeira. 2019. Subexponential-time algorithms for sparse PCA. arXiv preprint arXiv:1907.11635."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0909892106"},{"key":"e_1_3_2_1_16_1","volume-title":"Beyond Worst-case Analysis of Algorithms, Tim Roughgarden (Ed.).","author":"Feige Uriel","unstructured":"Uriel Feige . 2019. Introduction to Semirandom Models . In Beyond Worst-case Analysis of Algorithms, Tim Roughgarden (Ed.). Oxford . 266\u2013290. Uriel Feige. 2019. Introduction to Semirandom Models. In Beyond Worst-case Analysis of Algorithms, Tim Roughgarden (Ed.). Oxford. 266\u2013290."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743518"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1773"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.3.CO;2-1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240118X"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Vitaly Feldman Elena Grigorescu Lev Reyzin Santosh Vempala and Ying Xiao. 2013. Statistical algorithms and a lower bound for detecting planted cliques. In STOC. ACM 655\u2013664. \t\t\t\t  Vitaly Feldman Elena Grigorescu Lev Reyzin Santosh Vempala and Ying Xiao. 2013. Statistical algorithms and a lower bound for detecting planted cliques. In STOC. ACM 655\u2013664.","DOI":"10.1145\/2488608.2488692"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000086"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"David Gamarnik Aukosh Jagannath and Alexander S Wein. 2020. Low-degree hardness of random optimization problems. arXiv preprint arXiv:2004.12063. \t\t\t\t  David Gamarnik Aukosh Jagannath and Alexander S Wein. 2020. Low-degree hardness of random optimization problems. arXiv preprint arXiv:2004.12063.","DOI":"10.1109\/FOCS46700.2020.00021"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520006"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00048"},{"key":"e_1_3_2_1_34_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_35_1","volume-title":"Complexity of computer computations","author":"Karp Richard M","unstructured":"Richard M Karp . 1972. Reducibility among combinatorial problems . In Complexity of computer computations . Springer , 85\u2013103. Richard M Karp. 1972. Reducibility among combinatorial problems. In Complexity of computer computations. Springer, 85\u2013103."},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the International Congress of Mathematicians\u2014Seoul","volume":"1","author":"Khot Subhash","year":"2014","unstructured":"Subhash Khot . 2014 . Hardness of approximation . In Proceedings of the International Congress of Mathematicians\u2014Seoul 2014. Vol. 1 . Kyung Moon Sa, Seoul, 711\u2013728. Subhash Khot. 2014. Hardness of approximation. In Proceedings of the International Congress of Mathematicians\u2014Seoul 2014. Vol. 1. Kyung Moon Sa, Seoul, 711\u2013728."},{"key":"e_1_3_2_1_37_1","volume-title":"Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory, COLT 2018","author":"Klivans Adam R.","year":"2018","unstructured":"Adam R. Klivans , Pravesh K. Kothari , and Raghu Meka . 2018 . Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory, COLT 2018 , Stockholm, Sweden , 6-9 July 2018. 1420\u20131430. http:\/\/proceedings.mlr.press\/v75\/klivans18a.html Adam R. Klivans, Pravesh K. Kothari, and Raghu Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018. 1420\u20131430. http:\/\/proceedings.mlr.press\/v75\/klivans18a.html"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Pravesh K. Kothari Ryuhei Mori Ryan O\u2019Donnell and David Witmer. 2017. Sum of squares lower bounds for refuting any CSP. In STOC. ACM 132\u2013145. \t\t\t\t  Pravesh K. Kothari Ryuhei Mori Ryan O\u2019Donnell and David Witmer. 2017. Sum of squares lower bounds for refuting any CSP. In STOC. ACM 132\u2013145.","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_2_1_39_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_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_42_1","unstructured":"Dmitriy Kunisky Alexander S Wein and Afonso S Bandeira. 2019. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv:1907.11636. \t\t\t\t  Dmitriy Kunisky Alexander S Wein and Afonso S Bandeira. 2019. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv:1907.11636."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451084"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Allen Liu and Ankur Moitra. 2022. Minimax Rates for Robust Community Detection. arXiv preprint arXiv:2207.11903. \t\t\t\t  Allen Liu and Ankur Moitra. 2022. Minimax Rates for Robust Community Detection. arXiv preprint arXiv:2207.11903.","DOI":"10.1109\/FOCS54457.2022.00083"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.45"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897573"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897548"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.33"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.10"},{"key":"e_1_3_2_1_50_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"},{"key":"e_1_3_2_1_51_1","unstructured":"Tselil Schramm and Alexander S Wein. 2020. Computational barriers to estimation from low-degree polynomials. arXiv preprint arXiv:2008.02269. \t\t\t\t  Tselil Schramm and Alexander S Wein. 2020. Computational barriers to estimation from low-degree polynomials. arXiv preprint arXiv:2008.02269."},{"key":"e_1_3_2_1_52_1","unstructured":"Jacob Steinhardt. 2017. Does robustness imply tractability? A lower bound for planted clique in the semi-random model. arXiv preprint arXiv:1704.05120. \t\t\t\t  Jacob Steinhardt. 2017. Does robustness imply tractability? A lower bound for planted clique in the semi-random model. arXiv preprint arXiv:1704.05120."},{"key":"e_1_3_2_1_53_1","unstructured":"Alexander S Wein. 2020. Optimal Low-Degree Hardness of Maximum Independent Set. arXiv preprint arXiv:2010.06563. \t\t\t\t  Alexander S Wein. 2020. Optimal Low-Degree Hardness of Maximum Independent Set. arXiv preprint arXiv:2010.06563."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585184","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":53,"alternative-id":["10.1145\/3564246.3585184","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585184","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}