The Sherali-Adams Hierarchy for Promise CSPs through Tensors

We study the Sherali-Adams linear programming hierarchy in the context of promise constraint satisfaction problems (PCSPs). We characterise when a level of the hierarchy accepts an instance in terms of a homomorphism problem for an appropriate multilinear structure obtained through a tensor power of...

Descripción completa

Detalles Bibliográficos

Autores principales:	Ciardo, Lorenzo, Živný, Stanislav
Formato:	Artículo
Publicado:	2022
Materias:	Computational Complexity Discrete Mathematics Data Structures and Algorithms Logic in Computer Science
Acceso en línea:	https://arxiv.org/abs/2203.02478 http://arxiv.org/abs/2203.02478
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!