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).
The BWC was also shown @cite_9 @cite_31 to capture precisely the Max-CSPs that can be robustly approximated, as conjectured in @cite_24 . This work is similar to ours but different. In particular, Dalmau and Krokhin showed that various reductions preserve robust approximability of equations, and thus showing that Max-CSPs not satisfying the BWC cannot be robustly approximated, assuming P @math NP and relying on H stad's inapproximability results for linear equations @cite_30 . (Barto and Kozik @cite_31 then showed that Max-CSPs satisfying the BWC can be robustly approximated.) However, note that linear equations be solved exactly using Gaussian elimination and thus this result is not applicable in our setting. Our result, on the other hand, shows that various reductions preserve exact solvability of equations by a algorithm (the Lasserre SDP hierarchy) independently of P ,vs. ,NP . Moreover, the pp-definitions and pp-interpretations used in @cite_9 @cite_31 were required to be equality-free. We prove that our reductions are well-behaved without this assumption.
@cite_24 @cite_9 @cite_31 @cite_30
2611404581 2151577278 2964303025 1999032440
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.