{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:39Z","timestamp":1750309179841,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021_207429 \/ 1"],"award-info":[{"award-number":["200021_207429 \/ 1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>\n            For binary polynomial optimization problems of degree\n            <jats:italic>2d<\/jats:italic>\n            with\n            <jats:italic>n<\/jats:italic>\n            variables Sakaue, Takeda, Kim, and Ito [\n            <jats:xref ref-type=\"bibr\">33<\/jats:xref>\n            ] proved that the\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\lceil \\frac{n+2d-1}{2}\\rceil\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            th semidefinite (SDP) relaxation in the SoS\/Lasserre hierarchy of SDP relaxations provides the exact optimal value. When\n            <jats:italic>n<\/jats:italic>\n            is an odd number, we show that their analysis is tight, i.e., we prove that\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\frac{n+2d-1}{2}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            levels of the SoS\/Lasserre hierarchy are also necessary.\n          <\/jats:p>\n          <jats:p>\n            Laurent [\n            <jats:xref ref-type=\"bibr\">24<\/jats:xref>\n            ] showed that the Sherali-Adams hierarchy requires\n            <jats:italic>n<\/jats:italic>\n            levels to detect the empty integer hull of a linear representation of a set with no integral points. She conjectured that the SoS\/Lasserre rank for the same problem is\n            <jats:italic>n<\/jats:italic>\n            -1. In this article, we disprove this conjecture and derive lower and upper bounds for the rank.\n          <\/jats:p>","DOI":"10.1145\/3626106","type":"journal-article","created":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T21:33:48Z","timestamp":1697578428000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight Sum-of-squares Lower Bounds for Binary Polynomial Optimization Problems"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2320-4482","authenticated-orcid":false,"given":"Adam","family":"Kurpisz","sequence":"first","affiliation":[{"name":"Business School, Bern University of Applied Sciences and ETH Z\u00fcrich, Department of Mathematics, Bern, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-0169-6224","authenticated-orcid":false,"given":"Samuli","family":"Lepp\u00e4nen","sequence":"additional","affiliation":[{"name":"Axpo Solutions AG, Baden, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2948-9749","authenticated-orcid":false,"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[{"name":"SUPSI-IDSIA - Dalle Molle Institute for Artificial Intelligence, Lugano, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2024,3,12]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_3_3_2","volume-title":"A Comprehensive Analysis of Lift-and-project Methods for Combinatorial Optimization","author":"Au Yu Hin","year":"2014","unstructured":"Yu Hin Au. 2014. A Comprehensive Analysis of Lift-and-project Methods for Combinatorial Optimization. PhD thesis. University of Waterloo."},{"key":"e_1_3_3_4_2","first-page":"307","volume-title":"STOC\u201912","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. In STOC\u201912. 307\u2013326."},{"key":"e_1_3_3_5_2","first-page":"143","volume-title":"STOC\u201915","author":"Barak B.","year":"2015","unstructured":"B. Barak, J. A. Kelner, and D. Steurer. 2015. Dictionary learning and tensor decomposition via the sum-of-squares method. In STOC\u201915. 143\u2013151."},{"key":"e_1_3_3_6_2","first-page":"417","volume-title":"COLT\u201916","author":"Barak B.","year":"2016","unstructured":"B. Barak and A. Moitra. 2016. Noisy tensor completion via the sum-of-squares hierarchy. In COLT\u201916. 417\u2013445."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.1.19.10593"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100250"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s1-35.1.284"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0977-z"},{"key":"e_1_3_3_11_2","first-page":"954","volume-title":"FOCS\u201920","author":"Ghosh Mrinalkanti","year":"2020","unstructured":"Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran. 2020. Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes. In FOCS\u201920. 954\u2013965."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.4.796.10012"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8192-0"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00055-0"},{"key":"e_1_3_3_17_2","first-page":"178","volume-title":"STOC\u201916","author":"Hopkins S. B.","year":"2016","unstructured":"S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. 2016. Fast spectral algorithms from sum-of-squares proofs: Tensor decomposition and planted sparse vectors. In STOC\u201916. 178\u2013191."},{"key":"e_1_3_3_18_2","volume-title":"STOC\u201918","author":"Kothari P.","year":"2018","unstructured":"P. Kothari, J. Steinhardt, and D. Steurer. 2018. Robust moment estimation and improved clustering via sum of squares. In STOC\u201918."},{"key":"e_1_3_3_19_2","article-title":"A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian","volume":"1907","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. CoRR abs\/1907.11686 (2019).","journal-title":"CoRR"},{"key":"e_1_3_3_20_2","first-page":"79:1\u201379:15","volume-title":"ICALP\u201919","author":"Kurpisz Adam","year":"2019","unstructured":"Adam Kurpisz. 2019. Sum-of-squares bounds via Boolean function analysis. In ICALP\u201919. 79:1\u201379:15."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0797"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01398-9"},{"key":"e_1_3_3_23_2","first-page":"90:1\u201390:20","volume-title":"ICALP\u201921","author":"Kurpisz Adam","year":"2021","unstructured":"Adam Kurpisz, Aaron Potechin, and Elias Samuel Wirth. 2021. SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization. In ICALP\u201921. 90:1\u201390:20."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.4.871.20508"},{"key":"e_1_3_3_27_2","first-page":"567","volume-title":"STOC\u201915","author":"Lee James R.","year":"2015","unstructured":"James R. Lee, Prasad Raghavendra, and David Steurer. 2015. Lower bounds on the size of semidefinite programming relaxations. In STOC\u201915. 567\u2013576."},{"key":"e_1_3_3_28_2","first-page":"17:1\u201317:31","volume-title":"CCC\u201916","author":"Lee Troy","year":"2016","unstructured":"Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen. 2016. On the sum-of-squares degree of symmetric quadratic functions. In CCC\u201916. 17:1\u201317:31."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_3_3_30_2","first-page":"293","volume-title":"STOC\u201909","author":"Mathieu Claire","year":"2009","unstructured":"Claire Mathieu and Alistair Sinclair. 2009. Sherali-Adams relaxations of the matching polytope. In STOC\u201909. 293\u2013302."},{"key":"e_1_3_3_31_2","first-page":"87","volume-title":"STOC\u201915","author":"Meka Raghu","year":"2015","unstructured":"Raghu Meka, Aaron Potechin, and Avi Wigderson. 2015. Sum-of-squares lower bounds for planted clique. In STOC\u201915. 87\u201396."},{"key":"e_1_3_3_32_2","volume-title":"Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization","author":"Parrilo Pablo","year":"2000","unstructured":"Pablo Parrilo. 2000. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis. California Institute of Technology."},{"key":"e_1_3_3_33_2","first-page":"1619","volume-title":"COLT\u201917","author":"Potechin A.","year":"2017","unstructured":"A. Potechin and D. Steurer. 2017. Exact tensor completion with sum-of-squares. In COLT\u201917. 1619\u20131673."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M105544X"},{"key":"e_1_3_3_35_2","first-page":"1760","volume-title":"COLT\u201917","author":"Schramm T.","year":"2017","unstructured":"T. Schramm and D. Steurer. 2017. Fast and robust tensor decomposition with applications to dictionary learning. In COLT\u201917. 1760\u20131793."},{"key":"e_1_3_3_36_2","first-page":"43","volume-title":"IPCO\u201921","author":"Slot Lucas","year":"2021","unstructured":"Lucas Slot and Monique Laurent. 2021. Sum-of-squares hierarchies for binary polynomial optimization. In IPCO\u201921. 43\u201357."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/2781633.2781634"},{"journal-title":"https:\/\/en.wikipedia.org\/wiki\/Partial_fraction_decomposition#Procedure","article-title":"Partial fraction decomposition","key":"e_1_3_3_38_2","unstructured":"Wikipedia. 2023. Partial fraction decomposition. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Partial_fraction_decomposition#Procedure"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626106","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:53:59Z","timestamp":1750287239000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3626106"],"URL":"https:\/\/doi.org\/10.1145\/3626106","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2024,3,12]]},"assertion":[{"value":"2021-10-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}