Approximate Graph Colouring and the Crystal with a Hollow Shadow

Abstract

We show that approximate graph colouring is not solved by the lift-and-project hierarchy for the combination of linear programming and linear Diophantine equations. The proof is based on combinatorial tensor theory.

Full version of a STOC'23 paper and a SODA'23 paper (arXiv:2210.08293). Generalises and subsumes results from Section 6 in arXiv:2203.02478

References in corpus (5)

• Algebraic approach to promise constraint satisfaction
• The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
• The complexity of promise SAT on non-Boolean domains
• CLAP: A New Algorithm for Promise CSPs
• Conditional Dichotomy of Boolean Ordered Promise CSPs

Cited by in corpus (1)

• Hierarchies of Minion Tests for PCSPs through Tensors