{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:47Z","timestamp":1750221167709,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T00:00:00Z","timestamp":1527033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Royal Society University Research Fellowship"},{"name":"European Research Council"},{"name":"European Union's Horizon 2020 research and innovation programme","award":["714532"],"award-info":[{"award-number":["714532"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"<jats:p>\n            It has been shown that for a general-valued constraint language \u0393 the following statements are equivalent: (1) any instance of VCSP(\u0393) can be solved to\n            <jats:italic>optimality<\/jats:italic>\n            using a\n            <jats:italic>constant level<\/jats:italic>\n            of the Sherali-Adams LP hierarchy, (2) any instance of VCSP(\u0393) can be solved to optimality using the\n            <jats:italic>third level<\/jats:italic>\n            of the Sherali-Adams LP hierarchy, and (3) the support of \u0393 satisfies the \u201c\n            <jats:italic>bounded width condition<\/jats:italic>\n            \u201d (i.e., it contains weak near-unanimity operations of all arities).\n          <\/jats:p>\n          <jats:p>We show that if the support of \u0393 violates the bounded width condition then not only is VCSP(\u0393) not solved by a constant level of the Sherali-Adams LP hierarchy, but it also requires linear levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For \u0393 corresponding to linear equations in an Abelian group, this result follows from existing work on inapproximability of Max-CSPs. By a breakthrough result of Lee, Raghavendra, and Steurer [STOC\u201915], our result implies that for any \u0393 whose support violates the bounded width condition no SDP relaxation of polynomial size solves VCSP(\u0393).<\/jats:p>\n          <jats:p>We establish our result by proving that various reductions preserve exact solvability by the Lasserre SDP hierarchy (up to a constant factor in the level of the hierarchy). Our results hold for general-valued constraint languages (i.e., sets of functions on a fixed finite domain that take on rational or infinite values) and thus also hold in notable special cases of { 0, \u221e }-valued languages (CSPs), {0, 1}-valued languages (Min-CSPs\/Max-CSPs), and Q-valued languages (finite-valued CSPs).<\/jats:p>","DOI":"10.1145\/3201777","type":"journal-article","created":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T15:08:42Z","timestamp":1527088122000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Limits of SDP Relaxations for General-Valued CSPs"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1993-9571","authenticated-orcid":false,"given":"Johan","family":"Thapper","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Est, Marne-la-Vall\u00e9e, Champs-sur-Marne, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]}],"member":"320","published-online":{"date-parts":[[2018,5,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.049"},{"volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","year":"2017","author":"Atserias Albert","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/130915479"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"volume-title":"Complexity of Constraints","series-title":"Lecture Notes in Computer Science","author":"Bodirsky Manuel","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2933604"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","author":"Chlamt\u00e1\u010d Eden","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/130906398"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540090"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005108"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"volume-title":"Approximation Algorithms and Semidefinite Programming","author":"G\u00e4rtner Bernd","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-22015-9"},{"volume-title":"Proceedings of the 32nd Annual IEEE Conference on Computational Complexity (CCC\u201917)","year":"2017","author":"Ghosh Mrinal Kanti","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a011"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055438"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-015-0327-2"},{"volume-title":"Automata, Languages, and Programming","series-title":"Lecture Notes in Computer Science","author":"Kozik Marcin","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090274"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-007-2012-6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400380079"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_2_1_41_1","unstructured":"James R. Lee Prasad Raghavendra and David Steurer. 2014. Lower bounds on the size of semidefinite programming relaxations. arXiv:1411.6317. http:\/\/arxiv.org\/abs\/1411.6317  James R. Lee Prasad Raghavendra and David Steurer. 2014. Lower bounds on the size of semidefinite programming relaxations. arXiv:1411.6317. http:\/\/arxiv.org\/abs\/1411.6317"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627928"},{"key":"e_1_2_1_46_1","unstructured":"Prasad Raghavendra and David Steurer. 2017. Personal communication.  Prasad Raghavendra and David Steurer. 2017. Personal communication."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2974019"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079245"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005087"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","key":"e_1_2_1_55_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04565-7"},{"volume-title":"Shmoys","year":"2011","author":"Williamson David P.","key":"e_1_2_1_56_1"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3201777","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3201777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:53Z","timestamp":1750208933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3201777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,23]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3201777"],"URL":"https:\/\/doi.org\/10.1145\/3201777","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,5,23]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}