The limits of SDP relaxations for general-valued CSPs

It has been shown that for a general-valued constraint language Gamma the following statements are equivalent: (1) any instance of operatornameVCSP(Gamma) can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy; (2) any instance of operatornameVCSP(Gamma) can be solved to optimality using the third level of the Sherali-Adams LP hierarchy; (3) the support of Gamma satisfies the "bounded width condition", i.e., it contains weak near-unanimity operations of all arities. We show that if the support of Gamma violates the bounded width condition then not only is operatornameVCSP(Gamma) not solved by a constant level of the Sherali-Adams LP hierarchy but it is also not solved by Omega(n) levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For Gamma 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'15], our result implies that for any Gamma whose support violates the bounded width condition no SDP relaxation of polynomial-size solves operatornameVCSP(Gamma). 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,∞-valued languages (CSPs), 0,1-valued languages (Min-CSPs/Max-CSPs), and mathbbQ-valued languages (finite-valued CSPs).