Hierarchies of minion tests for PCSPs through tensors

Conference item

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” of the hierarchy, and a geometric part - which we call tensorisation - inspired by multilinear algebra.
We show that the hierarchies of minion tests obtained in this way are general enough to capture the (combinatorial) bounded width and also the Sherali-Adams LP, Sum-of-Squares SDP, and affine IP hierarchies. We exploit the geometry of the tensor spaces arising from our construction to prove general properties of such hierarchies. We identify certain classes of minions, which we call linear and conic, whose corresponding hierarchies have particularly fine features. Finally, in order to analyse the Sum-of-Squares SDP hierarchy we also characterise the solvability of the standard SDP relaxation through a new minion.

Authors: Ciardo, L; Živný, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
• Pages: 568-580
• Publication date: 2023-01-16
• Acceptance date: 2022-10-11
• Event title: ACM-SIAM Symposium on Discrete Algorithms (SODA23)
• Event location: Florence, Italy
• Event website: https://www.siam.org/conferences/cm/conference/soda23
• Event start date: 2023-01-22
• Event end date: 2023-01-25
• DOI: 10.1137/1.9781611977554.ch25
• EISBN: 9781611977554
• Language: English
• Keywords: FFR