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).
We now informally describe the bounded width condition (BWC). A set of operations on a fixed finite domain satisfies the BWC if it contains weak near-unanimity'' operations of all possible arities. An operation is called a weak near-unanimity operation if the value of the operation does not change assuming all the arguments but at most one are the same. A simple example is a ternary majority operation, which satisfies @math for all @math and @math . Polymorphisms @cite_14 are operations that combine satisfying assignments to a CSP instance and produce a new satisfying assignment. We say that a CSP instance @math satisfies the BWC if the clone of polymorphisms of @math satisfies the BWC.
@cite_14
1988961015 2531021157 2007385254 2097646889
A k-ary weak near-unanimity operation (or k-WNU) on A is an operation that satisfies the equations w(x, . . . x) ≈ x and w(y, x, . . . , x) ≈ w(x, y, . . . , x) ≈ · · · ≈ w(x, x, . . . , x, y) . If an algebra A has a k-NU (or a k-WNU) term operation, we say that A satisfies NU(k) (or WNU(k), respectively). Likewise, a variety is said to satisfy NU(k) (or WNU(k), respectively), it it has a k-variable term satisfying these equations. It has been conjectured that a finite idempotent algebra A has finite relational width if and only if V(A) (the variety generated by A) has meet semi-distributive congruence lattices. The concept of “finite relational width” arises in the theory of complexity of algorithms, in the algebraic study of constraint-satisfaction problems. Actually, there are several different definitions of this concept and it is not known if they are equivalent. One version of the concept and the conjecture mentioned above are due to B. Larose and L. Zadori [10]. The important family of varieties with meet semi-distributive congruence lattices has various known characterizations. There is a characterization by a certain Maltsev condition; also, it is known that a locally finite variety has this property iff it omits congruence covers of types 1 and 2 (defined in the tame congruence theory of D. Hobby, R. McKenzie [6]). E. Kiss showed that a finite idempotent algebra of relational width k must have an m-WNU term operation for every m ≥ k. E. Kiss and M. Valeriote then observed that a finite algebra with a k-WNU term operation, k > 1, must omit congruence covers of type 1. These observations led M. Valeriote to make two conjectures: any locally finite variety omits congruence covers of type 1 iff it satisfies WNU(k) for some k > 1; any locally finite variety has meet semi-distributive congruence lattices if and only if for some k, it satisfies WNU(m) for all m ≥ k. In this paper, we prove both of these conjectures of M. Valeriote. The family of locally finite varieties omitting type 1 is the largest family of locally finite varieties defined by a nontrivial idempotent Maltsev condition. For this In our LICS 2004 paper we introduced an approach to the study of the local structure of finite algebras and relational structures that aims at applications in the Constraint Satisfaction Problem (CSP). This approach involves a graph associated with an algebra @math or a relational structure A, whose vertices are the elements of @math (or A), the edges represent subsets of @math such that the restriction of some term operation of @math is ‘good’ on the subset, that is, act as an operation of one of the 3 types: semilattice, majority, or affine. In this paper we significantly refine and advance this approach. In particular, we prove certain connectivity and rectangularity properties of relations over algebras related to components of the graph connected by semilattice and affine edges. We also prove a result similar to 2-decomposition of relations invariant under a majority operation, only here we do not impose any restrictions on the relation. These results allow us to give a new, somewhat more intuitive proof of the bounded width theorem: the CSP over algebra @math has bounded width if and only if @math does not contain affine edges. Actually, this result shows that bounded width implies width (2,3). We also consider algebras with edges from a restricted set of types. In particular, it can be proved that type restrictions are preserved under the standard algebraic constructions. Finally, we prove that algebras without semilattice edges have few subalgebras of powers, that is, the CSP over such algebras is also polynomial time. We initiate a study of when the value of mathematical relaxations such as linear and semi-definite programs for constraint satisfaction problems (CSPs) is approximately preserved when restricting the instance to a sub-instance induced by a small random subsample of the variables. Let C be a family of CSPs such as 3SAT, Max-Cut, etc., and let Π be a mathematical program that is a relaxation for C, in the sense that for every instance P ∈ C, Π(P) is a number in [0, 1] upper bounding the maximum fraction of satisfiable constraints of P. Loosely speaking, we say that subsampling holds for C and Π if for every sufficiently dense instance P ∈ C and every e > 0, if we let P' be the instance obtained by restricting P to a sufficiently large constant number of variables, then Π(P') ∈ (1 ± e)Π(P). We say that weak subsampling holds if the above guarantee is replaced with Π(P') = 1 − θ(γ) whenever Π(P) = 1 − γ, where θ hides only absolute constants. We obtain both positive and negative results, showing that: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the semi-definite program considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every constraint-satisfaction problem under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type. 3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semi-definite programs. Also there are unique CSPs for which (even weak) subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semi-definite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value 1 − γ have a cut value at most 1 − γ 10. More generally, our results give an approach to obtaining average-case algorithms for CSPs using semi-definite programming hierarchies. By the breakthrough work of Hastad [J ACM 48(4) (2001), 798–859], several constraint satisfaction problems are now known to have the following approximation resistance property: Satisfying more clauses than what picking a random assignment would achieve is NP-hard. This is the case for example for Max E3-Sat, Max E3-Lin, and Max E4-Set Splitting. A notable exception to this extreme hardness is constraint satisfaction over two variables (2-CSP); as a corollary of the celebrated Goemans-Williamson algorithm [J ACM 42(6) (1995), 1115–1145], we know that every Boolean 2-CSP has a nontrivial approximation algorithm whose performance ratio is better than that obtained by picking a random assignment to the variables. An intriguing question then is whether this is also the case for 2-CSPs over larger, non-Boolean domains. This question is still open, and is equivalent to whether the generalization of Max 2-SAT to domains of size d, can be approximated to a factor better than (1 − 1 d2). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, that the Not-All-Equal Sat problem over domain size d with three variables per constraint, is approximation resistant, for every d ≥ 3. In the Boolean case, Not-All-Equal Sat with three variables per constraint is equivalent to Max 2-SAT and thus has a nontrivial approximation algorithm; for larger domain sizes, Max 2-SAT can be reduced to Not-All-Equal Sat with three variables per constraint. Our approximation algorithm implies that a wide class of 2-CSPs called regular 2-CSPs can all be approximated beyond their random assignment threshold. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004