{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T22:31:42Z","timestamp":1780612302314,"version":"3.54.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T00:00:00Z","timestamp":1604534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T00:00:00Z","timestamp":1604534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1712730"],"award-info":[{"award-number":["DMS-1712730"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1719545"],"award-info":[{"award-number":["DMS-1719545"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1719545"],"award-info":[{"award-number":["DMS-1719545"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1712730"],"award-info":[{"award-number":["DMS-1712730"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"DOI":"10.1007\/s10107-020-01558-2","type":"journal-article","created":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T16:02:51Z","timestamp":1604592171000},"page":"721-759","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A tight degree 4 sum-of-squares lower bound for the Sherrington\u2013Kirkpatrick Hamiltonian"],"prefix":"10.1007","volume":"190","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0854-4067","authenticated-orcid":false,"given":"Dmitriy","family":"Kunisky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7331-7557","authenticated-orcid":false,"given":"Afonso S.","family":"Bandeira","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,11,5]]},"reference":[{"key":"1558_CR1","unstructured":"Addario-Berry, L., Maillard, P.: The algorithmic hardness threshold for continuous random energy models. arXiv preprint arXiv:1810.05129 (2018)"},{"key":"1558_CR2","unstructured":"Bandeira, A.S., Kunisky, D.: A Gramian description of the degree 4 generalized elliptope. arXiv preprint arXiv:1812.11583 (2018)"},{"key":"1558_CR3","doi-asserted-by":"crossref","unstructured":"Bandeira, A.S., Kunisky, D.: Sum-of-squares optimization and the sparsity structure of equiangular tight frames. In: 2019 International Conference on Sampling Theory and Applications (SampTA 2019). IEEE (2019)","DOI":"10.1109\/SampTA45681.2019.9030987"},{"key":"1558_CR4","unstructured":"Bandeira, A.S., Kunisky, D., Wein, A.S.: Computational hardness of certifying bounds on constrained PCA problems. In: Vidick, T. (ed.) 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Leibniz International Proceedings in Informatics (LIPIcs)"},{"issue":"2","key":"1558_CR5","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/17M1138236","volume":"48","author":"B Barak","year":"2019","unstructured":"Barak, B., Hopkins, S., Kelner, J., Kothari, P.K., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM J. Comput. 48(2), 687\u2013735 (2019)","journal-title":"SIAM J. Comput."},{"key":"1558_CR6","unstructured":"Barak, B., Steurer, D.: Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236 (2014)"},{"key":"1558_CR7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972290","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"G Blekherman","year":"2012","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. SIAM, Philadelphia (2012)"},{"key":"1558_CR8","doi-asserted-by":"crossref","unstructured":"Casazza, P.G., Redmond, D., Tremain, J.C.: Real equiangular frames. In: 42nd Annual Conference on Information Sciences and Systems (CISS 2008), pp. 715\u2013720. IEEE (2008)","DOI":"10.1109\/CISS.2008.4558615"},{"key":"1558_CR9","first-page":"257","volume":"4","author":"S Chatterjee","year":"2008","unstructured":"Chatterjee, S., Meckes, E.: Multivariate normal approximation using exchangeable pairs. Alea 4, 257\u2013283 (2008)","journal-title":"Alea"},{"issue":"2","key":"1558_CR10","doi-asserted-by":"publisher","first-page":"1190","DOI":"10.1214\/15-AOP1084","volume":"45","author":"A Dembo","year":"2017","unstructured":"Dembo, A., Montanari, A., Sen, S., et al.: Extremal cuts of sparse random graphs. Ann. Probab. 45(2), 1190\u20131217 (2017)","journal-title":"Ann. Probab."},{"key":"1558_CR11","volume-title":"Geometry of Cuts and Metrics","author":"MM Deza","year":"2009","unstructured":"Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics, vol. 15. Springer, Berlin (2009)"},{"issue":"1\u20132","key":"1558_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-015-0977-z","volume":"160","author":"H Fawzi","year":"2016","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.A.: Sparse sums of squares on finite abelian groups and improved semidefinite lifts. Math. Program. 160(1\u20132), 149\u2013191 (2016)","journal-title":"Math. Program."},{"key":"1558_CR13","doi-asserted-by":"crossref","unstructured":"Fickus, M., Mixon, D.G.: Tables of the existence of equiangular tight frames. arXiv preprint arXiv:1504.00253 (2015)","DOI":"10.1109\/SAMPTA.2015.7148910"},{"key":"1558_CR14","unstructured":"Hopkins, S.: Statistical inference and the sum of squares method. Ph.D. thesis, Cornell University (2018)"},{"key":"1558_CR15","doi-asserted-by":"crossref","unstructured":"Hopkin, S.B., Steurer, D.: Efficient Bayesian estimation from few samples: community detection and related problems. In: 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pp. 379\u2013390. IEEE (2017)","DOI":"10.1109\/FOCS.2017.42"},{"key":"1558_CR16","doi-asserted-by":"crossref","unstructured":"Jain, V., Koehler, F., Risteski, A.: Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective. In: 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), pp. 1226\u20131236. ACM (2019)","DOI":"10.1145\/3313276.3316299"},{"key":"1558_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1558_CR18","unstructured":"Kunisky, D., Wein, A.S., Bandeira, A.S.: Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio. arXiv preprint arXiv:1907.11636 (2019)"},{"key":"1558_CR19","doi-asserted-by":"crossref","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: Sum-of-squares hierarchy lower bounds for symmetric formulations. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 362\u2013374. Springer (2016)","DOI":"10.1007\/978-3-319-33461-5_30"},{"issue":"3","key":"1558_CR20","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"1558_CR21","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1214\/aos\/1015957395","volume":"28","author":"B Laurent","year":"2000","unstructured":"Laurent, B., Massart, P.: Adaptive estimation of a quadratic functional by model selection. Ann. Stat. 28(5), 1302\u20131338 (2000)","journal-title":"Ann. Stat."},{"issue":"4","key":"1558_CR22","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4), 871\u2013883 (2003)","journal-title":"Math. Oper. Res."},{"key":"1558_CR23","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, pp. 157\u2013270. Springer (2009)","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"1558_CR24","unstructured":"Ledoux, M.: The concentration of measure phenomenon. No.\u00a089 in Mathematical Surveys & Monographs. American Mathematical Society (2001)"},{"key":"1558_CR25","volume-title":"Probability in Banach Spaces: Isoperimetry and Processes","author":"M Ledoux","year":"2013","unstructured":"Ledoux, M., Talagrand, M.: Probability in Banach Spaces: Isoperimetry and Processes. Springer, Berlin (2013)"},{"issue":"3","key":"1558_CR26","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1137\/S0895479892240683","volume":"15","author":"CK Li","year":"1994","unstructured":"Li, C.K., Tam, B.S.: A note on extreme correlation matrices. SIAM J. Matrix Anal. Appl. 15(3), 903\u2013908 (1994)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1558_CR27","doi-asserted-by":"crossref","unstructured":"Mohanty, S., Raghavendra, P., Xu, J.: Lifting sum-of-squares lower bounds: degree-2 to degree-4. arXiv preprint arXiv:1911.01411 (2019)","DOI":"10.1145\/3357713.3384319"},{"key":"1558_CR28","doi-asserted-by":"crossref","unstructured":"Montanari, A.: Optimization of the Sherrington\u2013Kirkpatrick Hamiltonian. In: 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pp. 1417\u20131433. IEEE (2019)","DOI":"10.1109\/FOCS.2019.00087"},{"key":"1558_CR29","doi-asserted-by":"crossref","unstructured":"Montanari, A., Sen, S.: Semidefinite programs on sparse random graphs and their application to community detection. In: 48th Annual ACM Symposium on Theory of Computing (STOC 2016), pp. 814\u2013827. ACM (2016)","DOI":"10.1145\/2897518.2897548"},{"key":"1558_CR30","unstructured":"O\u2019Donnell, R.: SOS is not obviously automatizable, even approximately. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl\u2013Leibniz\u2013Zentrum fuer Informatik (2017)"},{"issue":"1","key":"1558_CR31","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2013.177.1.8","volume":"177","author":"D Panchenko","year":"2013","unstructured":"Panchenko, D.: The Parisi ultrametricity conjecture. Ann. Math. 177(1), 383\u2013393 (2013)","journal-title":"Ann. Math."},{"key":"1558_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6289-7","volume-title":"The Sherrington\u2013Kirkpatrick Model","author":"D Panchenko","year":"2013","unstructured":"Panchenko, D.: The Sherrington\u2013Kirkpatrick Model. Springer, Berlin (2013)"},{"issue":"23","key":"1558_CR33","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1103\/PhysRevLett.43.1754","volume":"43","author":"G Parisi","year":"1979","unstructured":"Parisi, G.: Infinite number of order parameters for spin-glasses. Phys. Rev. Lett. 43(23), 1754 (1979)","journal-title":"Phys. Rev. Lett."},{"key":"1558_CR34","unstructured":"Raghavendra, P., Weitz, B.: On the bit complexity of sum-of-squares proofs. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a080, pp. 80:1\u201380:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017)"},{"key":"1558_CR35","unstructured":"Montanari, A., Richard, E.: A statistical model for tensor PCA. In: NIPS\u201914: Proceedings of the 27th International Conference on Neural Information Processing Systems, vol. 2, pp. 2897\u20132905. Montreal, Canada (2014)"},{"key":"1558_CR36","doi-asserted-by":"crossref","unstructured":"Rudelson, M.: Invertibility of random matrices: norm of the inverse. Ann. Math. 575\u2013600 (2008)","DOI":"10.4007\/annals.2008.168.575"},{"issue":"2","key":"1558_CR37","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.aim.2008.01.010","volume":"218","author":"M Rudelson","year":"2008","unstructured":"Rudelson, M., Vershynin, R.: The Littlewood\u2013Offord problem and invertibility of random matrices. Adv. Math. 218(2), 600\u2013633 (2008)","journal-title":"Adv. Math."},{"issue":"26","key":"1558_CR38","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1103\/PhysRevLett.35.1792","volume":"35","author":"D Sherrington","year":"1975","unstructured":"Sherrington, D., Kirkpatrick, S.: Solvable model of a spin-glass. Physical Rev. Lett. 35(26), 1792 (1975)","journal-title":"Physical Rev. Lett."},{"key":"1558_CR39","unstructured":"Subag, E.: Following the ground-states of full-RSB spherical spin glasses. arXiv preprint arXiv:1812.04588 (2018)"},{"key":"1558_CR40","doi-asserted-by":"publisher","DOI":"10.1201\/9781466593480","volume-title":"Linear Algebra and Geometry","author":"P Suetin","year":"1989","unstructured":"Suetin, P., Kostrikin, A.I., Manin, Y.I.: Linear Algebra and Geometry. CRC Press, Boca Raton (1989)"},{"issue":"2\u20133","key":"1558_CR41","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1016\/j.laa.2007.05.043","volume":"426","author":"MA Sustik","year":"2007","unstructured":"Sustik, M.A., Tropp, J.A., Dhillon, I.S., Heath Jr., R.W.: On the existence of equiangular tight frames. Linear Algebra Appl. 426(2\u20133), 619\u2013635 (2007)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1558_CR42","doi-asserted-by":"publisher","first-page":"221","DOI":"10.4007\/annals.2006.163.221","volume":"163","author":"M Talagrand","year":"2006","unstructured":"Talagrand, M.: The Parisi formula. Ann. Math. 163(1), 221\u2013263 (2006)","journal-title":"Ann. Math."},{"issue":"3\u20134","key":"1558_CR43","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00440-010-0281-z","volume":"150","author":"R Vershynin","year":"2011","unstructured":"Vershynin, R.: Spectral norm of products of random and deterministic matrices. Probab. Theory Relat. Fields 150(3\u20134), 471\u2013509 (2011)","journal-title":"Probab. Theory Relat. Fields"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01558-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01558-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01558-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:55:21Z","timestamp":1633834521000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01558-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,5]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1558"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01558-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,5]]},"assertion":[{"value":"31 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}