{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:46Z","timestamp":1781077846000,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["2047933"],"award-info":[{"award-number":["2047933"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649703","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1923-1934","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8689-6770","authenticated-orcid":false,"given":"Pravesh K.","family":"Kothari","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8205-1608","authenticated-orcid":false,"given":"Aaron","family":"Potechin","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8327-4126","authenticated-orcid":false,"given":"Jeff","family":"Xu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","article-title":"Community Detection and Stochastic Block Models","volume":"18","author":"Abbe Emmanuel","year":"2017","unstructured":"Emmanuel Abbe. 2017. Community Detection and Stochastic Block Models: Recent Developments. J. Mach. Learn. Res., 18, 1 (2017), jan, 6446\u20136531. issn:1532-4435","journal-title":"Recent Developments. J. Mach. Learn. Res."},{"key":"e_1_3_2_1_2_1","unstructured":"Emmanuel Abbe Afonso S. Bandeira and Georgina Hall. 2014. Exact Recovery in the Stochastic Block Model. arxiv:1405.3267."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.47"},{"key":"e_1_3_2_1_4_1","volume-title":"Proof of the Achievability Conjectures for the General Stochastic Block Model. Communications on Pure and Applied Mathematics, 71","author":"Abbe Emmanuel","year":"2018","unstructured":"Emmanuel Abbe and Colin Sandon. 2018. Proof of the Achievability Conjectures for the General Stochastic Block Model. Communications on Pure and Applied Mathematics, 71 (2018)."},{"key":"e_1_3_2_1_5_1","volume-title":"Graph Matrices: Norm Bounds and Applications. abs\/1604.03423","author":"Ahn Kwangjun","year":"2020","unstructured":"Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. 2020. Graph Matrices: Norm Bounds and Applications. abs\/1604.03423 (2020), arxiv:1604.03423. arxiv:1604.03423"},{"key":"e_1_3_2_1_6_1","unstructured":"Sanjeev Arora Satish Rao and Umesh Vazirani. 2004. Expander flows and a \u221a ologn-approximation to sparsest cut."},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201921)","author":"Bakshi Ainesh","year":"1976","unstructured":"Ainesh Bakshi and Pravesh K. Kothari. 2021. List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201921). Society for Industrial and Applied Mathematics, USA. 1279\u20131297. isbn:9781611976465"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1180396"},{"key":"e_1_3_2_1_9_1","volume-title":"Semidefinite Programming, and Community Detection. CoRR, abs\/1911.01960","author":"Banks Jess","year":"2019","unstructured":"Jess Banks, Sidhanth Mohanty, and Prasad Raghavendra. 2019. Local Statistics, Semidefinite Programming, and Community Detection. CoRR, abs\/1911.01960 (2019), arXiv:1911.01960. arxiv:1911.01960"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746625"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"B. Barak S. B. Hopkins J. Kelner P. Kothari A. Moitra and A. Potechin. 2016. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. 428\u2013437.","DOI":"10.1109\/FOCS.2016.53"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Boaz Barak Prasad Raghavendra and David Steurer. 2011. Rounding Semidefinite Programming Hierarchies via Global Correlation. 472\u2013481.","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Charles Bordenave. 2019. A new proof of Friedman\u2019s second eigenvalue Theorem and its extension to random lifts. arXiv. To appear in Annales scientifiques de l\u2019\u00c9cole normale sup\u00e9rieure","DOI":"10.24033\/asens.2450"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.86"},{"key":"e_1_3_2_1_16_1","unstructured":"Wenjun Cai and Aaron Potechin. 2020. The Spectrum of the Singular Values of Z-Shaped Graph Matrices. arxiv:2006.14144."},{"key":"e_1_3_2_1_17_1","unstructured":"Wenjun Cai and Aaron Potechin. 2022. On Mixing Distributions Via Random Orthogonal Matrices and the Spectrum of the Singular Values of Multi-Z Shaped Graph Matrices. arxiv:2206.02224."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006826"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20550"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22935-0_40"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.107.065701"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015","author":"Deshpande Yash","year":"2015","unstructured":"Yash Deshpande and Andrea Montanari. 2015. Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015. 523\u2013562. http:\/\/proceedings.mlr.press\/v40\/Deshpande15.html"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.140"},{"key":"e_1_3_2_1_25_1","unstructured":"Jingqiu Ding Tommaso d\u2019Orsi Rajai Nasser and David Steurer. 2021. Robust recovery for stochastic block models. arxiv:2111.08568."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11511-017-0145-9"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055451"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701387660"},{"key":"e_1_3_2_1_29_1","volume-title":"Spectral techniques applied to sparse random graphs. Random Structures & Algorithms, 27","author":"Feige Uriel","year":"2005","unstructured":"Uriel Feige and Eran. O. Ofek. 2005. Spectral techniques applied to sparse random graphs. Random Structures & Algorithms, 27 (2005)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780646"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00093"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"M. X. Goemans and D. P. Williamson. 1994. .878-Approximation Algorithms for MAX CUT and MAX 2SAT. 422\u2013431.","DOI":"10.1145\/195058.195216"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami and Ali Kemal Sinop. 2011. Lasserre Hierarchy Higher Eigenvalues and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. In FOCS. 482\u2013491.","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_1_35_1","unstructured":"Samuel B. Hopkins. 2019. Mean Estimation with Sub-Gaussian Rates in Polynomial Time. arxiv:1809.07425."},{"key":"e_1_3_2_1_36_1","volume-title":"The Power of Sum-of-Squares for Detecting Hidden Structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 720\u2013731","author":"Hopkins Samuel B","year":"2017","unstructured":"Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. 2017. The Power of Sum-of-Squares for Detecting Hidden Structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 720\u2013731."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_38_1","volume-title":"Conference on Learning Theory. 956\u20131006","author":"Hopkins Samuel B","year":"2015","unstructured":"Samuel B Hopkins, Jonathan Shi, and David Steurer. 2015. Tensor principal component analysis via sum-of-squares proofs. In Conference on Learning Theory. 956\u20131006."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_40_1","volume-title":"Kothari","author":"Hsieh Jun-Ting","year":"2021","unstructured":"Jun-Ting Hsieh and Pravesh K. Kothari. 2021. Algorithmic Thresholds for Refuting Random Polynomial Systems. arxiv:2110.08677."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00048"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Chris Jones Aaron Potechin Goutham Rajendran and Jeff Xu. 2023. Sum-of-Squares Lower Bounds for Densest k-Subgraph. arxiv:2303.17506.","DOI":"10.1145\/3564246.3585221"},{"key":"e_1_3_2_1_43_1","unstructured":"Adam Klivans Pravesh K. Kothari and Raghu Meka. 2020. Efficient Algorithms for Outlier-Robust Regression. arxiv:1803.03241."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Pravesh Kothari Ryuhei Mori Ryan O\u2019Donnell and David Witmer. 2017. Sum of squares lower bounds for refuting any CSP.","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_2_1_45_1","volume-title":"Kothari and Peter Manohar","author":"Pravesh","year":"2021","unstructured":"Pravesh K. Kothari and Peter Manohar. 2021. A Stress-Free Sum-of-Squares Lower Bound for Coloring. arxiv:2105.07517."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1312486110"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1103\/physrevlett.102.238701"},{"key":"e_1_3_2_1_49_1","volume-title":"Bandeira","author":"Kunisky Dmitriy","year":"2019","unstructured":"Dmitriy Kunisky and Afonso S. Bandeira. 2019. A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian. abs\/1907.11686 (2019), arxiv:1907.11686. arxiv:1907.11686"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00047"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Tengyu Ma Jonathan Shi and David Steurer. 2016. Polynomial-time tensor decompositions with sum-of-squares. 438\u2013446.","DOI":"10.1109\/FOCS.2016.54"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591857"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746600"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Sidhanth Mohanty Prasad Raghavendra and Jeff Xu. 2020. Lifting sum-of-squares lower bounds: degree-2 to degree-4. 840\u2013853.","DOI":"10.1145\/3357713.3384319"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-014-0576-6"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3238-8"},{"key":"e_1_3_2_1_58_1","volume-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. Dissertation","author":"Parrilo Pablo A","unstructured":"Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. Dissertation. California Institute of Technology."},{"key":"e_1_3_2_1_59_1","unstructured":"Aaron Potechin and Goutham Rajendran. 2023. Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. arxiv:2011.04253."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055417"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","unstructured":"Goutham Rajendran and Madhur Tulsiani. [n. d.]. Concentration of polynomial random matrices via Efron-Stein inequalities. 3614\u20133653. https:\/\/doi.org\/10.1137\/1.9781611977554.ch138 arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977554.ch138. 10.1137\/1.9781611977554.ch138","DOI":"10.1137\/1.9781611977554.ch138"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"crossref","unstructured":"Grant Schoenebeck. 2008. Linear Level Lasserre Lower Bounds for Certain k-CSPs.","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649703","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649703"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":63,"alternative-id":["10.1145\/3618260.3649703","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649703","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}