The limits of SDP relaxations for general-valued CSPs

Autor: Stanislav Živný, Johan Thapper
Přispěvatelé: Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Department of Computer Science [Oxford], University of Oxford [Oxford], 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-Centre National de la Recherche Scientifique ( CNRS ), University of Oxford (UNITED KINGDOM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2016
Předmět:
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
FOS: Computer and information sciences
Computer Science - Logic in Computer Science
Polynomial
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
010103 numerical & computational mathematics
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Computer Science::Computational Complexity
Computational Complexity (cs.CC)
01 natural sciences
Domain (mathematical analysis)
Theoretical Computer Science
Combinatorics
Abelian group
0101 mathematics
Computer Science::Data Structures and Algorithms
[ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
ComputingMilieux_MISCELLANEOUS
Mathematics
Hierarchy (mathematics)
010102 general mathematics
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]
Logic in Computer Science (cs.LO)
Computer Science - Computational Complexity
[ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC]
Computational Theory and Mathematics
010201 computation theory & mathematics
Bounded function
[ INFO.INFO-LO ] Computer Science [cs]/Logic in Computer Science [cs.LO]
Relaxation (approximation)
Constant (mathematics)
F.2.0
Linear equation
Zdroj: ACM Transactions on Computation Theory
ACM Transactions on Computation Theory, ACM, 2018, 10 (3), pp.1-22. ⟨10.1145/3201777⟩
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2017, Reykjavik, Iceland. ⟨10.1109/LICS.2017.8005087⟩
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2017, Reykjavik, Iceland. IEEE, 〈10.1109/LICS.2017.8005087〉
ISSN: 1942-3454
1942-3462
DOI: 10.48550/arxiv.1612.01147
Popis: It has been shown that for a general-valued constraint language $\Gamma$ the following statements are equivalent: (1) any instance of $\operatorname{VCSP}(\Gamma)$ can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy; (2) any instance of $\operatorname{VCSP}(\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 $\operatorname{VCSP}(\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 $\operatorname{VCSP}(\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,\infty\}$-valued languages (CSPs), $\{0,1\}$-valued languages (Min-CSPs/Max-CSPs), and $\mathbb{Q}$-valued languages (finite-valued CSPs).
Comment: Full version of a LICS'17 paper. Builds on and extends arXiv:1606.02577. arXiv admin note: text overlap with arXiv:1606.02577
Databáze: OpenAIRE
Externí odkaz: