论文标题
通过张量
The Sherali-Adams Hierarchy for Promise CSPs through Tensors
论文作者
论文摘要
我们在承诺限制满意度问题（PCSP）的背景下研究Sherali-Adams线性编程层次结构。我们表征何时层次结构级别接受通过约束语言的张量功率获得的适当多线性结构的同态问题的实例。该结构的几何形状由满足某些对称性的张量的张量组成，然后允许通过不断层次的sherali-adams来建立近似图的着色问题的不可分化性。 除了这一主要应用外，我们的张力构造还为研究算法放松的层次结构引入了一种新工具，以解决约束满意度的背景（以及超越）内部的计算问题。特别是，我们将其视为朝着代数表征Sherali-Adams对PCSP的代数表征的关键步骤。
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 the constraint language. The geometry of this structure, which consists in a space of tensors satisfying certain symmetries, allows then to establish non-solvability of the approximate graph colouring problem via constantly many levels of Sherali-Adams. Besides this primary application, our tensorisation construction introduces a new tool to the study of hierarchies of algorithmic relaxations for computational problems within (and, possibly, beyond) the context of constraint satisfaction. In particular, we see it as a key step towards the algebraic characterisation of the power of Sherali-Adams for PCSPs.
