论文标题
PCSP的小责任测试通过张量的层次结构
Hierarchies of Minion Tests for PCSPs through Tensors
论文作者
论文摘要
我们提供一个统一的框架来研究放松的层次结构，以解决约束满意度问题及其诺言。这个想法是将层次结构的描述分为代数部分，具体取决于捕获“基本级别”的小兵和几何部分 - 我们称为张力 - 受多线性代数的启发。我们利用由我们的构造产生的张量空间的几何形状，以证明层次结构的一般特性。我们确定了某些类似的奴才，我们称之为线性和圆锥，其相应的层次结构具有特别优秀的特征。我们确定（组合）有界宽度，Sherali-Adams LP，Aggine IP，Suger-Squares SDP和组合的“ LP +仿射IP”层次结构均由该框架捕获。特别是，为了分析平方英尺的SDP层次结构，我们还通过新的小兵表征了标准SDP松弛的可溶性。
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.
