{"id":"arxiv/2610.02565","url":"https://arxiv.org/abs/2610.02565","tags":["quant-ph","cs.CC"],"score":0,"title":"The complexity of entangled graph colouring via polymorphisms","domain":"quant-ph","source":"arxiv","authors":["Eric Culf"],"reviews":0,"subject":"quant-ph","summary":"Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal games. Due to the CSP dichotomy theorem, the complexity of constraint satisfaction problems with classical assignments can be fully understood by studying the symmetries of the CSP, in terms of the polymorphisms of the underlying relational structure. In this work, we show that the polymorphism-based reductions between CSPs can be generalised to gap-preserving reductions between entangled CSPs based…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}