It has been shown that for a general-valued constraint language Γ the following statements are equivalent: (1) any instance of VCSP(Γ) can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy; (2) any instance of VCSP(Γ) can be solved to optimality using the third level of the Sherali-Adams LP hierarchy; (3) the support of Γ satisfies the "bounded width condition", i.e., it contains weak near-unanimity operations of all arities. We show that if the support of Γ violates the bounded with condition then not only is VCSP(Γ) not solved by a constant level of the Sherali-Adams LP hierarchy but it is also not solved by Ω(n) levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP hierarchy). For Γ 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 Γ whose support violates the bounded width condition no SDP relaxation of polynomial-size solves VCSP(Γ). 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 Q-valued languages (finite-valued CSPs).
 An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(e))-fraction of constraints for each (1 − e)-satisfiable instance (i.e., such that at most a e-fraction of constraints needs to be removed to make the instance satisfiable), where f(e) → 0 as e → 0. We establish an algebraic framework for analyzing constraint satisfaction problems admitting an efficient robust algorithm with functions f of a given growth rate. We use this framework to derive hardness results. We also describe three classes of problems admitting an efficient robust algorithm such that f is O(1 log (1 e)), O(e1 k) for some k > 1, and O(e), respectively. Finally, we give a complete classification of robust satisfiability with a given f for the Boolean case. An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least @math -fraction of the constraints given a @math -satisfiable instance, where @math as @math . Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction problem admits an efficient robust algorithm. This paper confirms their conjecture. We prove optimal, up to an arbitrary e > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.