Hierarchies of Minion Tests for PCSPs through Tensors

Abstract

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.

arXiv commentFull version of a SODA 2023 paper. Generalises and subsumes all but Sections 6 and 7 of arXiv:2203.02478

References in corpus (14)

• Algebraic approach to promise constraint satisfaction
• The power of linear programming for general-valued CSPs
• The complexity of finite-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
• The expressibility of functions on the Boolean domain, with applications to Counting CSPs
• The complexity of promise SAT on non-Boolean domains
• CLAP: A New Algorithm for Promise CSPs
• Conditional Dichotomy of Boolean Ordered Promise CSPs
• Local consistency as a reduction between constraint satisfaction problems
• The complexity of approximating conservative counting CSPs
• Linearly ordered colourings of hypergraphs
• Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
• Approximate Graph Colouring and the Crystal with a Hollow Shadow