Hierarchies of Minion Tests for PCSPs through Tensors
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918348243075072 |
|---|---|
| author | Ciardo, Lorenzo Živný, Stanislav |
| author_facet | Ciardo, Lorenzo Živný, Stanislav |
| contents | We provide a unified framework to study hierarchies of relaxations for Constraint Satisfaction Problems and their Promise variant. The idea is to split the description of a hierarchy into an algebraic part, depending on a minion capturing the "base level", and a geometric part - which we call tensorisation - inspired by multilinear algebra. We exploit the geometry of the tensor spaces arising from our construction to prove general properties of hierarchies. We identify certain classes of minions, which we call linear and conic, whose corresponding hierarchies have particularly fine features. We establish that the (combinatorial) bounded width, Sherali-Adams LP, affine IP, Sum-of-Squares SDP, and combined "LP + affine IP" hierarchies are all captured by this framework. In particular, in order to analyse the Sum-of-Squares SDP hierarchy, we also characterise the solvability of the standard SDP relaxation through a new minion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_02277 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Hierarchies of Minion Tests for PCSPs through Tensors Ciardo, Lorenzo Živný, Stanislav Computational Complexity Discrete Mathematics Combinatorics We provide a unified framework to study hierarchies of relaxations for Constraint Satisfaction Problems and their Promise variant. The idea is to split the description of a hierarchy into an algebraic part, depending on a minion capturing the "base level", and a geometric part - which we call tensorisation - inspired by multilinear algebra. We exploit the geometry of the tensor spaces arising from our construction to prove general properties of hierarchies. We identify certain classes of minions, which we call linear and conic, whose corresponding hierarchies have particularly fine features. We establish that the (combinatorial) bounded width, Sherali-Adams LP, affine IP, Sum-of-Squares SDP, and combined "LP + affine IP" hierarchies are all captured by this framework. In particular, in order to analyse the Sum-of-Squares SDP hierarchy, we also characterise the solvability of the standard SDP relaxation through a new minion. |
| title | Hierarchies of Minion Tests for PCSPs through Tensors |
| topic | Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2207.02277 |