{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:03Z","timestamp":1750695003732,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","funder":[{"name":"NSF","award":["CAREER Award #2047933"],"award-info":[{"award-number":["CAREER Award #2047933"]}]},{"name":"NSF","award":["CCF-2008920."],"award-info":[{"award-number":["CCF-2008920."]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718151","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"84-95","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sum-of-Squares Lower Bounds for Coloring Random Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-8205-1608","authenticated-orcid":false,"given":"Aaron","family":"Potechin","sequence":"first","affiliation":[{"name":"University of Chicago, Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_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"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1145\/2775105"},{"unstructured":"Sanjeev Arora Satish Rao and Umesh Vazirani. 2004. Expander flows and a \u221a log n-approximation to sparsest cut.","key":"e_1_3_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1145\/3406325.3451099"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1137\/1.9781611977073.47"},{"key":"e_1_3_2_1_6_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_7_1","volume-title":"Wein","author":"Bandeira Afonso S.","year":"2020","unstructured":"Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein. 2020. Spectral planting and hardness of refuting cuts, colorability, and communities in random graphs. arXiv preprint arXiv:2008.12237."},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 36th International Conference on Neural Information Processing Systems (NIPS \u201922)","author":"Bandeira Afonso S.","year":"2024","unstructured":"Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, and Ilias Zadik. 2024. The franz-parisi criterion and computational trade-offs in high dimensional statistics. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NIPS \u201922). Curran Associates Inc., Red Hook, NY, USA. Article 2452, 14 pages. isbn:9781713871088"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1137\/18M1180396"},{"key":"e_1_3_2_1_10_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_11_1","volume-title":"Jonathan A. Kelner, David Steurer, and Yuan Zhou.","author":"Barak Boaz","year":"2012","unstructured":"Boaz Barak, Fernando G. S. L. Brand\u00e3o, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. 2012. Hypercontractivity, Sum-of-Squares Proofs, and their Applications. CoRR, abs\/1205.4484 (2012)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/2746539.2746625"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1137\/17M1138236"},{"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.","key":"e_1_3_2_1_14_1","DOI":"10.1109\/FOCS.2016.53"},{"doi-asserted-by":"crossref","unstructured":"Boaz Barak Pravesh K. Kothari and David Steurer. 2017. Quantum Entanglement Sum of Squares and the Log Rank Conjecture. ACM 975\u2013988.","key":"e_1_3_2_1_15_1","DOI":"10.1145\/3055399.3055488"},{"doi-asserted-by":"crossref","unstructured":"Boaz Barak Prasad Raghavendra and David Steurer. 2011. Rounding Semidefinite Programming Hierarchies via Global Correlation. 472\u2013481.","key":"e_1_3_2_1_16_1","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_17_1","first-page":"59","article-title":"Sum-of-squares proofs and the quest toward optimal algorithms","volume":"21","author":"Barak Boaz","year":"2014","unstructured":"Boaz Barak and David Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. Electronic Colloquium on Computational Complexity (ECCC), 21 (2014), 59.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"doi-asserted-by":"crossref","unstructured":"Enric Boix-Adser\u00e0 Matthew Brennan and Guy Bresler. 2021. The Average-Case Complexity of Counting Cliques in Erd\u0151s\u2013R\u00e9nyi Hypergraphs. SIAM J. Comput. FOCS19\u201339.","key":"e_1_3_2_1_18_1","DOI":"10.1137\/20M1316044"},{"key":"e_1_3_2_1_19_1","volume-title":"Conference on Learning Theory. 648\u2013847","author":"Brennan Matthew","year":"2020","unstructured":"Matthew Brennan and Guy Bresler. 2020. Reducibility and statistical-computational gaps from secret leakage. In Conference on Learning Theory. 648\u2013847."},{"key":"e_1_3_2_1_20_1","volume-title":"Jerry Zheng Li, and Tselil Schramm","author":"Brennan Matthew","year":"2020","unstructured":"Matthew Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Zheng Li, and Tselil Schramm. 2020. Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent. ArXiv, abs\/2009.06107 (2020), https:\/\/api.semanticscholar.org\/CorpusID:221655335"},{"key":"e_1_3_2_1_21_1","volume-title":"Conference On Learning Theory. 48\u2013166","author":"Brennan Matthew","year":"2018","unstructured":"Matthew Brennan, Guy Bresler, and Wasim Huleihel. 2018. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory. 48\u2013166."},{"doi-asserted-by":"publisher","unstructured":"Zongchen Chen Elchanan Mossel and Ilias Zadik. 2023. Almost-Linear Planted Cliques Elude the Metropolis Process. 4504\u20134539. https:\/\/doi.org\/10.1137\/1.9781611977554.ch171 arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977554.ch171. 10.1137\/1.9781611977554.ch171","key":"e_1_3_2_1_22_1","DOI":"10.1137\/1.9781611977554.ch171"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1017\/S0963548305006826"},{"unstructured":"Ilias Diakonikolas Sushrut Karmalkar Shuo Pang and Aaron Potechin. 2024. Sum-of-squares lower bounds for Non-Gaussian Component Analysis. arxiv:2410.21426. arxiv:2410.21426","key":"e_1_3_2_1_24_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1137\/S009753970240118X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1145\/3046674"},{"doi-asserted-by":"crossref","unstructured":"N. Fleming P. Kothari and T. Pitassi. 2019. Semialgebraic Proofs and Efficient Algorithm Design.","key":"e_1_3_2_1_27_1","DOI":"10.1561\/9781680836370"},{"key":"e_1_3_2_1_28_1","volume-title":"Wein","author":"Gamarnik David","year":"2022","unstructured":"David Gamarnik, Aukosh Jagannath, and Alexander S. Wein. 2022. Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics. arxiv:2004.12063."},{"key":"e_1_3_2_1_29_1","volume-title":"The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property. CoRR, abs\/1904.07174","author":"Gamarnik David","year":"2019","unstructured":"David Gamarnik and Ilias Zadik. 2019. The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property. CoRR, abs\/1904.07174 (2019), arXiv:1904.07174. arxiv:1904.07174"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1109\/FOCS46700.2020.00093"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1145\/227683.227684"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1016\/S0304-3975(00)00157-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1137\/1.9781611976465.140"},{"unstructured":"Samuel B. Hopkins. 2019. Mean Estimation with Sub-Gaussian Rates in Polynomial Time. arxiv:1809.07425.","key":"e_1_3_2_1_34_1"},{"key":"e_1_3_2_1_35_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1145\/3188745.3188748"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1002\/rsa.3240030402"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1109\/FOCS52979.2021.00048"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1145\/3564246.3585221"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1007\/BF02579314"},{"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_41_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.","key":"e_1_3_2_1_42_1","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_2_1_43_1","volume-title":"Annual Conference Computational Learning Theory. https:\/\/api.semanticscholar.org\/CorpusID:257255498","author":"Kothari Pravesh","year":"2023","unstructured":"Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, and Jeff Xu. 2023. Is Planted Coloring Easier than Planted Clique? In Annual Conference Computational Learning Theory. https:\/\/api.semanticscholar.org\/CorpusID:257255498"},{"key":"e_1_3_2_1_44_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_45_1","DOI":"10.4230\/LIPIcs.ITCS.2019.49"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1145\/3618260.3649703"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_47_1","DOI":"10.1145\/3188745.3188970"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_48_1","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_49_1","volume-title":"Bandeira","author":"Kunisky Dmitriy","year":"2019","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:1907.11636."},{"volume-title":"An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs","author":"Lasserre Jean B.","unstructured":"Jean B. Lasserre. 2001. An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs. Springer-Verlag, London, UK. 293\u2013303. isbn:3-540-42225-0","key":"e_1_3_2_1_50_1"},{"doi-asserted-by":"crossref","unstructured":"Tengyu Ma Jonathan Shi and David Steurer. 2016. Polynomial-time tensor decompositions with sum-of-squares. 438\u2013446.","key":"e_1_3_2_1_51_1","DOI":"10.1109\/FOCS.2016.54"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_52_1","DOI":"10.1007\/978-1-4757-3216-0_17"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_53_1","DOI":"10.4230\/LIPIcs.ITCS.2017.59"},{"key":"e_1_3_2_1_54_1","volume-title":"36th Computational Complexity Conference (LIPIcs. Leibniz Int. Proc. Inform.","volume":"26","author":"Pang Shuo","year":"2021","unstructured":"Shuo Pang. 2021. SOS lower bound for exact planted clique. In 36th Computational Complexity Conference (LIPIcs. Leibniz Int. Proc. Inform., Vol. 200). Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. 26, 63."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_55_1","DOI":"10.4230\/LIPIcs.CCC.2021.26"},{"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_56_1"},{"key":"e_1_3_2_1_57_1","volume-title":"Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. abs\/2011.04253","author":"Potechin Aaron","year":"2020","unstructured":"Aaron Potechin and Goutham Rajendran. 2020. Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. abs\/2011.04253 (2020), arxiv:2011.04253. arxiv:2011.04253"},{"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_58_1"},{"doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra Tselil Schramm and David Steurer. 2019. High-dimensional estimation via sum-of-squares proofs. arxiv:1807.11419.","key":"e_1_3_2_1_59_1","DOI":"10.1142\/9789813272880_0186"},{"unstructured":"Cynthia Rush Fiona Skerman Alexander S. Wein and Dana Yang. 2022. Is it easier to count communities than find them? arxiv:2212.10872.","key":"e_1_3_2_1_60_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_61_1","DOI":"10.1214\/22-aos2179"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_62_1","DOI":"10.1007\/BF01074929"},{"unstructured":"Alexander S Wein. 2020. Optimal Low-Degree Hardness of Maximum Independent Set. arXiv preprint arXiv:2010.06563.","key":"e_1_3_2_1_63_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '25","name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia"},"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.3718151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:40:43Z","timestamp":1750693243000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":63,"alternative-id":["10.1145\/3717823.3718151","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718151","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"}}]}}