Hierarchies of Minion Tests for PCSPs through Tensors
Open Access
- 7 April 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (2) , 1-45
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 structure 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.Keywords
Funding Information
- European Research Council (714532)
- UK Research and Innovation (EP/X024431/1)
This publication has 86 references indexed in Scilit:
- The wonderland of reflectionsIsrael Journal of Mathematics, 2017
- Improved Hardness of Approximating Chromatic Number2013
- Complexity of ConstraintsLecture Notes in Computer Science, 2008
- On the Power of k-Consistency2007
- The Hardness of 3-Uniform Hypergraph ColoringCombinatorica, 2005
- Conjunctive-Query Containment and Constraint SatisfactionJournal of Computer and System Sciences, 2000
- On the Hardness of Approximating the Chromatic NumberCombinatorica, 2000
- Complexity of Generalized Satisfiability Counting ProblemsInformation and Computation, 1996
- A Dichotomy Theorem for Maximum Generalized Satisfiability ProblemsJournal of Computer and System Sciences, 1995
- On the Expressive Power of Datalog: Tools and a Case StudyJournal of Computer and System Sciences, 1995