{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:05:49Z","timestamp":1759133149779,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384319","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"840-853","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Lifting sum-of-squares lower bounds: degree-2 to degree-4"],"prefix":"10.1145","author":[{"given":"Sidhanth","family":"Mohanty","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}]},{"given":"Jeff","family":"Xu","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Itai Benjamini Eyal Lubetzky and Sasha Sodin. 2007. Nonbacktracking random walks mix faster. Communications in Contemporary Mathematics 9 04 ( 2007 ) 585-603.  Noga Alon Itai Benjamini Eyal Lubetzky and Sasha Sodin. 2007. Nonbacktracking random walks mix faster. Communications in Contemporary Mathematics 9 04 ( 2007 ) 585-603.","DOI":"10.1142\/S0219199707002551"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_3_1","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. CoRR abs\/1604.03084 ( 2016 ). arXiv: 1604.03084 http:\/\/arxiv.org\/abs\/1604.03084  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. CoRR abs\/1604.03084 ( 2016 ). arXiv: 1604.03084 http:\/\/arxiv.org\/abs\/1604.03084"},{"key":"e_1_3_2_1_4_1","volume-title":"Conference on Learning Theory. 1046-1066","author":"Berthet Quentin","year":"2013","unstructured":"Quentin Berthet and Philippe Rigollet . 2013 . Complexity theoretic lower bounds for sparse principal component detection . In Conference on Learning Theory. 1046-1066 . Quentin Berthet and Philippe Rigollet. 2013. Complexity theoretic lower bounds for sparse principal component detection. In Conference on Learning Theory. 1046-1066."},{"key":"e_1_3_2_1_6_1","volume-title":"Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure. In Conference On Learning Theory, COLT 2018","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, COLT 2018 , Stockholm, Sweden , 6-9 July 2018. 48-166. http:\/\/proceedings.mlr.press\/v75\/brennan18a.html Matthew Brennan, Guy Bresler, and Wasim Huleihel. 2018. Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018. 48-166. http:\/\/proceedings.mlr.press\/v75\/brennan18a.html"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Endre Cs\u00f3ka Bal\u00e1zs Gerencs\u00e9r Viktor Harangi and B\u00e1lint Vir\u00e1g. 2015. Invariant Gaussian processes and independent sets on regular graphs of large girth. Random Structures & Algorithms 47 2 ( 2015 ) 284-303.  Endre Cs\u00f3ka Bal\u00e1zs Gerencs\u00e9r Viktor Harangi and B\u00e1lint Vir\u00e1g. 2015. Invariant Gaussian processes and independent sets on regular graphs of large girth. Random Structures & Algorithms 47 2 ( 2015 ) 284-303.","DOI":"10.1002\/rsa.20547"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1084"},{"key":"e_1_3_2_1_9_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-562. http:\/\/proceedings.mlr.press\/v40\/Deshpande15.html 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-562. http:\/\/proceedings.mlr.press\/v40\/Deshpande15.html"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.140"},{"key":"e_1_3_2_1_11_1","volume-title":"Van den Broeck","author":"Engel Andreas","year":"2001","unstructured":"Andreas Engel and Christian P. L . Van den Broeck . 2001 . Statistical Mechanics of Learning. Cambridge University Press , New York, NY, USA. Andreas Engel and Christian P. L. Van den Broeck. 2001. Statistical Mechanics of Learning. Cambridge University Press, New York, NY, USA."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1070\/rm2011v066n03abeh004749"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780646"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Dima Grigoriev. 2001. Complexity of Positivstellensatz proofs for the knapsack. computational complexity 10 2 ( 2001 ) 139-154.  Dima Grigoriev. 2001. Complexity of Positivstellensatz proofs for the knapsack. computational complexity 10 2 ( 2001 ) 139-154.","DOI":"10.1007\/s00037-001-8192-0"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178538"},{"key":"e_1_3_2_1_17_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). IEEE, 720-731","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). IEEE, 720-731 . 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). IEEE, 720-731."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_19_1","volume-title":"Extended Formulation Lower Bounds for Refuting Random CSPs. ACM Symposium on Discrete Algorithms (SODA) ( 2020 ).","author":"Issac-Brown Cohen Jonah","year":"2020","unstructured":"Jonah Issac-Brown Cohen and Prasad Raghavendra . 2020 . Extended Formulation Lower Bounds for Refuting Random CSPs. ACM Symposium on Discrete Algorithms (SODA) ( 2020 ). Jonah Issac-Brown Cohen and Prasad Raghavendra. 2020. Extended Formulation Lower Bounds for Refuting Random CSPs. ACM Symposium on Discrete Algorithms (SODA) ( 2020 )."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629614"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_2_1_22_1","volume-title":"A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian. arXiv preprint arXiv","author":"Kunisky Dmitriy","year":"1907","unstructured":"Dmitriy Kunisky and Afonso S Bandeira . 2019. A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian. arXiv preprint arXiv : 1907 . 11686 ( 2019 ). Dmitriy Kunisky and Afonso S Bandeira. 2019. A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian. arXiv preprint arXiv: 1907. 11686 ( 2019 )."},{"key":"e_1_3_2_1_23_1","series-title":"SIAM Journal on optimization 11, 3 ( 2001 ), 796-817","volume-title":"Global optimization with polynomials and the problem of moments","author":"Lasserre Jean B","unstructured":"Jean B Lasserre . 2001. Global optimization with polynomials and the problem of moments . SIAM Journal on optimization 11, 3 ( 2001 ), 796-817 . Jean B Lasserre. 2001. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization 11, 3 ( 2001 ), 796-817."},{"volume-title":"Information, Physics, and Computation","author":"Mezard Marc","key":"e_1_3_2_1_24_1","unstructured":"Marc Mezard and Andrea Montanari . 2009. Information, Physics, and Computation . Oxford University Press, Inc. , New York, NY, USA . Marc Mezard and Andrea Montanari. 2009. Information, Physics, and Computation. Oxford University Press, Inc., New York, NY, USA."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"M. Mezard G. Parisi and M. Virasoro. 1987. Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (World Scientific Lecture Notes in Physics). World Scientific. https:\/\/books.google.com\/books?id= DwY8DQAAQBAJ  M. Mezard G. Parisi and M. Virasoro. 1987. Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (World Scientific Lecture Notes in Physics). World Scientific. https:\/\/books.google.com\/books?id= DwY8DQAAQBAJ","DOI":"10.1142\/0271"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Andrea Montanari. 2018. Optimization of the Sherrington-Kirkpatrick Hamiltonian.  Andrea Montanari. 2018. Optimization of the Sherrington-Kirkpatrick Hamiltonian.","DOI":"10.1109\/FOCS.2019.00087"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897548"},{"volume-title":"Statistical Physics of Spin Glasses and Information Processing: an Introduction","author":"Nishimori Hidetoshi","key":"e_1_3_2_1_29_1","unstructured":"Hidetoshi Nishimori . 2001. Statistical Physics of Spin Glasses and Information Processing: an Introduction . Oxford University Press , Oxford; New York . Hidetoshi Nishimori. 2001. Statistical Physics of Spin Glasses and Information Processing: an Introduction. Oxford University Press, Oxford; New York."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2016.06.008"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.43.1754"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Giovanni P. Parisi. 1980. A sequence of approximated solutions to the S-K model for spin glasses.  Giovanni P. Parisi. 1980. A sequence of approximated solutions to the S-K model for spin glasses.","DOI":"10.1088\/0305-4470\/13\/4\/009"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055417"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070233"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Michel Talagrand. 2006. The Parisi formula. Annals of mathematics ( 2006 ) 221-263.  Michel Talagrand. 2006. The Parisi formula. Annals of mathematics ( 2006 ) 221-263.","DOI":"10.4007\/annals.2006.163.221"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_1_39_1","unstructured":"Roman Vershynin. 2010. Introduction to the non-asymptotic analysis of random matrices.  Roman Vershynin. 2010. Introduction to the non-asymptotic analysis of random matrices."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Nicholas C Wormald. 1999. Models of random regular graphs. ( 1999 ).  Nicholas C Wormald. 1999. Models of random regular graphs. ( 1999 ).","DOI":"10.1017\/CBO9780511721335.010"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384319","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384319","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:13Z","timestamp":1750200073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":38,"alternative-id":["10.1145\/3357713.3384319","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384319","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}