The limits of SDP relaxations for general-valued CSPs

• Published in: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
• Main Authors: Thapper, Johan, Živný, Stanislav
• Other Authors: Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout (BEZOUT), Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), University of Oxford
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2017
• Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]; Iceland
• Online Access: https://hal.science/hal-01796715; https://doi.org/10.1109/LICS.2017.8005087

International audience 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).