{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T15:35:28Z","timestamp":1774020928561,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":112,"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":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2008920, CCF-1816372, CAREER Award #2047933"],"award-info":[{"award-number":["CCF-2008920, CCF-1816372, CAREER Award #2047933"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["European Union's Horizon 2020 research and innovation programme (grant agreement No. 834861)"],"award-info":[{"award-number":["European Union's Horizon 2020 research and innovation programme (grant agreement No. 834861)"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585221","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"84-95","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Sum-of-Squares Lower Bounds for Densest k-Subgraph"],"prefix":"10.1145","author":[{"given":"Chris","family":"Jones","sequence":"first","affiliation":[{"name":"Bocconi University, Italy"}]},{"given":"Aaron","family":"Potechin","sequence":"additional","affiliation":[{"name":"University of Chicago, USA"}]},{"given":"Goutham","family":"Rajendran","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Jeff","family":"Xu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Graph Matrices: Norm Bounds and Applications. arXiv preprint arXiv:1604.03423.","author":"Ahn Kwangjun","year":"2020","unstructured":"Kwangjun Ahn , Dhruv Medarametla , and Aaron Potechin . 2020 . Graph Matrices: Norm Bounds and Applications. arXiv preprint arXiv:1604.03423. Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. 2020. Graph Matrices: Norm Bounds and Applications. arXiv preprint arXiv:1604.03423."},{"key":"e_1_3_2_1_2_1","volume-title":"Fernando Granha Jeronimo, and Madhur Tulsiani","author":"Alev Vedat Levi","year":"2019","unstructured":"Vedat Levi Alev , Fernando Granha Jeronimo, and Madhur Tulsiani . 2019 . Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. Manuscript Vedat Levi Alev, Fernando Granha Jeronimo, and Madhur Tulsiani. 2019. Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. Manuscript"},{"key":"e_1_3_2_1_3_1","volume-title":"Inapproximabilty of densest k-subgraph from average case hardness","author":"Alon Noga","year":"2011","unstructured":"Noga Alon , Sanjeev Arora , Rajsekar Manokaran , Dana Moshkovitz , and Omri Weinstein . 2011. Inapproximabilty of densest k-subgraph from average case hardness , 2011 . Manuscript , 6 (2011). Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein. 2011. Inapproximabilty of densest k-subgraph from average case hardness, 2011. Manuscript, 6 (2011)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-015-0777-x"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/ac3657"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_1_8_1","unstructured":"Sanjeev Arora Boaz Barak Markus Brunnermeier and Rong Ge. 2010. Computational complexity and information asymmetry in financial products. In ICS. 49\u201365. \t\t\t\t  Sanjeev Arora Boaz Barak Markus Brunnermeier and Rong Ge. 2010. Computational complexity and information asymmetry in financial products. In ICS. 49\u201365."},{"key":"e_1_3_2_1_9_1","unstructured":"Sanjeev Arora Satish Rao and Umesh Vazirani. 2004. Expander flows and a \u221a ologn-approximation to sparsest cut. \t\t\t\t  Sanjeev Arora Satish Rao and Umesh Vazirani. 2004. Expander flows and a \u221a ologn-approximation to sparsest cut."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451099"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.47"},{"key":"e_1_3_2_1_14_1","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. arXiv preprint arXiv:2012.02119. \t\t\t\t  Ainesh Bakshi Ilias Diakonikolas He Jia Daniel M Kane Pravesh K Kothari and Santosh S Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. arXiv preprint arXiv:2012.02119."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Ainesh Bakshi and Pravesh K Kothari. 2020. List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. arXiv preprint arXiv:2002.05139. \t\t\t\t  Ainesh Bakshi and Pravesh K Kothari. 2020. List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. arXiv preprint arXiv:2002.05139.","DOI":"10.1137\/1.9781611976465.78"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451001"},{"key":"e_1_3_2_1_17_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. \t\t\t\t  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_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746566"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Aditya Bhaskara Moses Charikar Eden Chlamtac Uriel Feige and Aravindan Vijayaraghavan. 2010. Detecting High Log-densities \u2013 An O(n^1\/4) Approximation for Densest k-Subgraph. \t\t\t\t  Aditya Bhaskara Moses Charikar Eden Chlamtac Uriel Feige and Aravindan Vijayaraghavan. 2010. Detecting High Log-densities \u2013 An O(n^1\/4) Approximation for Densest k-Subgraph.","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.34"},{"key":"e_1_3_2_1_21_1","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. \t\t\t\t  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.","DOI":"10.1137\/20M1316044"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s43069-020-00020-5"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.86"},{"key":"e_1_3_2_1_24_1","unstructured":"Matthew Brennan and Guy Bresler. 2019. Optimal average-case reductions to sparse pca: From weak assumptions to strong hardness. arXiv preprint arXiv:1902.07380. \t\t\t\t  Matthew Brennan and Guy Bresler. 2019. Optimal average-case reductions to sparse pca: From weak assumptions to strong hardness. arXiv preprint arXiv:1902.07380."},{"key":"e_1_3_2_1_25_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 . 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_26_1","unstructured":"Matthew Brennan Guy Bresler Samuel B Hopkins Jerry Li and Tselil Schramm. 2020. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.06107. \t\t\t\t  Matthew Brennan Guy Bresler Samuel B Hopkins Jerry Li and Tselil Schramm. 2020. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.06107."},{"key":"e_1_3_2_1_27_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 . 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."},{"key":"e_1_3_2_1_28_1","volume-title":"Conference on Learning Theory. 417\u2013468","author":"Brennan Matthew","year":"2019","unstructured":"Matthew Brennan , Guy Bresler , and Wasim Huleihel . 2019 . Universality of computational lower bounds for submatrix detection . In Conference on Learning Theory. 417\u2013468 . Matthew Brennan, Guy Bresler, and Wasim Huleihel. 2019. Universality of computational lower bounds for submatrix detection. In Conference on Learning Theory. 417\u2013468."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2616915.2629839"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_3_2_1_32_1","unstructured":"Chandra Chekuri and Shi Li. 2015. A note on the hardness of approximating the k-way Hypergraph Cut problem. Manuscript http:\/\/chekuri. cs. illinois. edu\/papers\/hypergraph-kcut. pdf. \t\t\t\t  Chandra Chekuri and Shi Li. 2015. A note on the hardness of approximating the k-way Hypergraph Cut problem. Manuscript http:\/\/chekuri. cs. illinois. edu\/papers\/hypergraph-kcut. pdf."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764480"},{"key":"e_1_3_2_1_34_1","unstructured":"Yudong Chen and Jiaming Xu. 2014. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. arXiv preprint arXiv:1402.1267. \t\t\t\t  Yudong Chen and Jiaming Xu. 2014. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. arXiv preprint arXiv:1402.1267."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21739"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096402"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.61"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.56"},{"key":"e_1_3_2_1_39_1","unstructured":"Eden Chlamt\u00e1\u010d and Pasin Manurangsi. 2018. Sherali-adams integrality gaps matching the log-density threshold. arXiv preprint arXiv:1804.07842. \t\t\t\t  Eden Chlamt\u00e1\u010d and Pasin Manurangsi. 2018. Sherali-adams integrality gaps matching the log-density threshold. arXiv preprint arXiv:1804.07842."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039743"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2644814"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132594"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1183"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_3_2_1_46_1","unstructured":"Uriel Feige and Michael Seltser. 1997. On the densest k-subgraph problem. Citeseer. \t\t\t\t  Uriel Feige and Michael Seltser. 1997. On the densest k-subgraph problem. Citeseer."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680836370"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00093"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_50_1","unstructured":"Doron Goldstein and Michael Langberg. 2009. The dense k subgraph problem. arXiv preprint arXiv:0912.5327. \t\t\t\t  Doron Goldstein and Michael Langberg. 2009. The dense k subgraph problem. arXiv preprint arXiv:0912.5327."},{"key":"e_1_3_2_1_51_1","volume-title":"Complexity of Positivstellensatz proofs for the knapsack. computational complexity, 10, 2","author":"Grigoriev Dima","year":"2001","unstructured":"Dima Grigoriev . 2001. Complexity of Positivstellensatz proofs for the knapsack. computational complexity, 10, 2 ( 2001 ), 139\u2013154. Dima Grigoriev. 2001. Complexity of Positivstellensatz proofs for the knapsack. computational complexity, 10, 2 (2001), 139\u2013154."},{"key":"e_1_3_2_1_52_1","volume-title":"Conference on Learning Theory. 899\u2013928","author":"Hajek Bruce","year":"2015","unstructured":"Bruce Hajek , Yihong Wu , and Jiaming Xu . 2015 . Computational lower bounds for community detection on random graphs . In Conference on Learning Theory. 899\u2013928 . Bruce Hajek, Yihong Wu, and Jiaming Xu. 2015. Computational lower bounds for community detection on random graphs. In Conference on Learning Theory. 899\u2013928."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2546280"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109626"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11758525_102"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_16"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.140"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1843"},{"key":"e_1_3_2_1_59_1","unstructured":"Samuel B Hopkins Pravesh K Kothari and Aaron Potechin. 2015. Sos and planted clique: Tight analysis of MPW moments at all degrees and an optimal lower bound at degree four. arXiv preprint arXiv:1507.05230. \t\t\t\t  Samuel B Hopkins Pravesh K Kothari and Aaron Potechin. 2015. Sos and planted clique: Tight analysis of MPW moments at all degrees and an optimal lower bound at degree four. arXiv preprint arXiv:1507.05230."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","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. 720\u2013731. \t\t\t\t  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. 720\u2013731.","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_62_1","volume-title":"Statistical Inference and the Sum of Squares Method. Ph. D. Dissertation","author":"Klevit Hopkins Samuel Brink","unstructured":"Samuel Brink Klevit Hopkins . 2018. Statistical Inference and the Sum of Squares Method. Ph. D. Dissertation . Cornell University . Samuel Brink Klevit Hopkins. 2018. Statistical Inference and the Sum of Squares Method. Ph. D. Dissertation. Cornell University."},{"key":"e_1_3_2_1_63_1","volume-title":"Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems. Ph. D. Dissertation","author":"Jones Chris","unstructured":"Chris Jones . 2022. Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems. Ph. D. Dissertation . The University of Chicago . Chris Jones. 2022. Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems. Ph. D. Dissertation. The University of Chicago."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00048"},{"key":"e_1_3_2_1_65_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_66_1","unstructured":"Yash Khanna and Anand Louis. 2020. Planted Models for the Densest k -Subgraph Problem. arXiv preprint arXiv:2004.13978. \t\t\t\t  Yash Khanna and Anand Louis. 2020. Planted Models for the Densest k -Subgraph Problem. arXiv preprint arXiv:2004.13978."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629614"},{"key":"e_1_3_2_1_69_1","volume-title":"Conference On Learning Theory. 1420\u20131430","author":"Klivans Adam","year":"2018","unstructured":"Adam Klivans , Pravesh K Kothari , and Raghu Meka . 2018 . Efficient algorithms for outlier-robust regression . In Conference On Learning Theory. 1420\u20131430 . Adam Klivans, Pravesh K Kothari, and Raghu Meka. 2018. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory. 1420\u20131430."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.08.006"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78773-0_37"},{"key":"e_1_3_2_1_72_1","volume-title":"On choosing a dense subgraph","author":"Kortsarz Guy","unstructured":"Guy Kortsarz and David Peleg . 1993. On choosing a dense subgraph . IEEE. Guy Kortsarz and David Peleg. 1993. On choosing a dense subgraph. IEEE."},{"key":"e_1_3_2_1_73_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. \t\t\t\t  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_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055438"},{"key":"e_1_3_2_1_75_1","unstructured":"Pravesh K Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581. \t\t\t\t  Pravesh K Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581."},{"key":"e_1_3_2_1_76_1","unstructured":"Dmitriy Kunisky. 2020. Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube. arXiv preprint arXiv:2009.07269. \t\t\t\t  Dmitriy Kunisky. 2020. Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube. arXiv preprint arXiv:2009.07269."},{"key":"e_1_3_2_1_77_1","volume-title":"Spectral Barriers in Certification Problems. Ph. D. Dissertation","author":"Kunisky Dmitriy","unstructured":"Dmitriy Kunisky . 2021. Spectral Barriers in Certification Problems. Ph. D. Dissertation . New York University . Dmitriy Kunisky. 2021. Spectral Barriers in Certification Problems. Ph. D. Dissertation. New York University."},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-97127-4_1"},{"key":"e_1_3_2_1_79_1","series-title":"SIAM Journal on optimization, 11, 3","volume-title":"Global optimization with polynomials and the problem of moments","author":"Lasserre Jean B","year":"2001","unstructured":"Jean B Lasserre . 2001. Global optimization with polynomials and the problem of moments . SIAM Journal on optimization, 11, 3 ( 2001 ), 796\u2013817. Jean B Lasserre. 2001. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11, 3 (2001), 796\u2013817."},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.101"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00313"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451084"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055412"},{"key":"e_1_3_2_1_85_1","unstructured":"Pasin Manurangsi and Dana Moshkovitz. 2015. Approximating dense max 2-CSPs. arXiv preprint arXiv:1507.08348. \t\t\t\t  Pasin Manurangsi and Dana Moshkovitz. 2015. Approximating dense max 2-CSPs. arXiv preprint arXiv:1507.08348."},{"key":"e_1_3_2_1_86_1","unstructured":"Pasin Manurangsi Aviad Rubinstein and Tselil Schramm. 2020. The strongish planted clique hypothesis and its consequences. arXiv preprint arXiv:2011.05555. \t\t\t\t  Pasin Manurangsi Aviad Rubinstein and Tselil Schramm. 2020. The strongish planted clique hypothesis and its consequences. arXiv preprint arXiv:2011.05555."},{"key":"e_1_3_2_1_87_1","unstructured":"Cheng Mao Alexander S. Wein and Shenduo Zhang. 2023. Detection-Recovery Gap for Planted Dense Cycles. arxiv:2302.06737. \t\t\t\t  Cheng Mao Alexander S. Wein and Shenduo Zhang. 2023. Detection-Recovery Gap for Planted Dense Cycles. arxiv:2302.06737."},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746600"},{"key":"e_1_3_2_1_89_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. \t\t\t\t  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_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"e_1_3_2_1_91_1","volume-title":"8th Innovations in Theoretical Computer Science Conference (ITCS","author":"O\u2019Donnell Ryan","year":"2017","unstructured":"Ryan O\u2019Donnell . 2017 . SOS is not obviously automatizable, even approximately . In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Ryan O\u2019Donnell. 2017. SOS is not obviously automatizable, even approximately. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)."},{"key":"e_1_3_2_1_92_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. 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."},{"key":"e_1_3_2_1_93_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 . 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_94_1","volume-title":"The quadratic knapsack problem\u2014a survey. Discrete applied mathematics, 155, 5","author":"Pisinger David","year":"2007","unstructured":"David Pisinger . 2007. The quadratic knapsack problem\u2014a survey. Discrete applied mathematics, 155, 5 ( 2007 ), 623\u2013648. David Pisinger. 2007. The quadratic knapsack problem\u2014a survey. Discrete applied mathematics, 155, 5 (2007), 623\u2013648."},{"key":"e_1_3_2_1_95_1","unstructured":"Aaron Potechin and Goutham Rajendran. 2020. Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. arXiv preprint arXiv:2011.04253. \t\t\t\t  Aaron Potechin and Goutham Rajendran. 2020. Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. arXiv preprint arXiv:2011.04253."},{"key":"e_1_3_2_1_96_1","unstructured":"Aaron Potechin and Goutham Rajendran. 2022. Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis. Advances in Neural Information Processing Systems. \t\t\t\t  Aaron Potechin and Goutham Rajendran. 2022. Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis. Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_97_1","doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? 245\u2013254. \t\t\t\t  Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? 245\u2013254.","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_1_98_1","volume-title":"Proceedings of the International Congress of Mathematicians: Rio de Janeiro","author":"Raghavendra Prasad","year":"2018","unstructured":"Prasad Raghavendra , Tselil Schramm , and David Steurer . 2018 . High dimensional estimation via sum-of-squares proofs . In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. 3389\u20133423. Prasad Raghavendra, Tselil Schramm, and David Steurer. 2018. High dimensional estimation via sum-of-squares proofs. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. 3389\u20133423."},{"key":"e_1_3_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_1_100_1","unstructured":"Prasad Raghavendra and Benjamin Weitz. 2017. On the Bit Complexity of Sum-of-Squares Proofs. \t\t\t\t  Prasad Raghavendra and Benjamin Weitz. 2017. On the Bit Complexity of Sum-of-Squares Proofs."},{"key":"e_1_3_2_1_101_1","unstructured":"Goutham Rajendran. 2018. Combinatorial Optimization via the Sum of Squares Hierarchy. arXiv preprint arXiv:2208.04374. \t\t\t\t  Goutham Rajendran. 2018. Combinatorial Optimization via the Sum of Squares Hierarchy. arXiv preprint arXiv:2208.04374."},{"key":"e_1_3_2_1_102_1","volume-title":"Nonlinear Random Matrices and Applications to the Sum of Squares Hierarchy. Ph. D. Dissertation","author":"Rajendran Goutham","unstructured":"Goutham Rajendran . 2022. Nonlinear Random Matrices and Applications to the Sum of Squares Hierarchy. Ph. D. Dissertation . The University of Chicago . Goutham Rajendran. 2022. Nonlinear Random Matrices and Applications to the Sum of Squares Hierarchy. Ph. D. Dissertation. The University of Chicago."},{"key":"e_1_3_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch138"},{"key":"e_1_3_2_1_104_1","unstructured":"Tselil Schramm. 2017. Random Matrices and the Sum-of-Squares Hierarchy. Ph. D. Dissertation. UC Berkeley. \t\t\t\t  Tselil Schramm. 2017. Random Matrices and the Sum-of-Squares Hierarchy. Ph. D. Dissertation. UC Berkeley."},{"key":"e_1_3_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1214\/22-AOS2179"},{"key":"e_1_3_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01074929"},{"key":"e_1_3_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.09.003"},{"key":"e_1_3_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.5555\/646687.702946"},{"key":"e_1_3_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383374"},{"key":"e_1_3_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0278-4"},{"key":"e_1_3_2_1_111_1","doi-asserted-by":"crossref","unstructured":"Madhur Tulsiani. 2009. CSP Gaps and Reductions in the Lasserre Hierarchy. \t\t\t\t  Madhur Tulsiani. 2009. CSP Gaps and Reductions in the Lasserre Hierarchy.","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_1_112_1","volume-title":"Conference on Learning Theory. 1247\u20131248","author":"Zadik Ilias","year":"2022","unstructured":"Ilias Zadik , Min Jae Song , Alexander S Wein , and Joan Bruna . 2022 . Lattice-based methods surpass sum-of-squares in clustering . In Conference on Learning Theory. 1247\u20131248 . Ilias Zadik, Min Jae Song, Alexander S Wein, and Joan Bruna. 2022. Lattice-based methods surpass sum-of-squares in clustering. In Conference on Learning Theory. 1247\u20131248."}],"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.3585221","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585221","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:01Z","timestamp":1750178821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":112,"alternative-id":["10.1145\/3564246.3585221","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585221","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"}}]}}