In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023), and obtain the following results:

The largest known gap between quantum and classical chromatic number of graphs, obtained via quantum protocols for colouring Hadamard graphs based on the Deutsch–Jozsa algorithm and the quantum Fourier transform, is exponential. We put forth a quantum pseudo-telepathy version of Khot’s \(d\)-to-1 Games Conjecture and prove that, conditional on its validity, the gap is unbounded: There exist graphs whose quantum chromatic number is 3 and whose classical chromatic number is arbitrarily large. Furthermore, we show that the existence of a certain form of pseudo-telepathic XOR games would imply the conjecture and, thus, the unboundedness of the quantum chromatic gap. As two technical steps of our proof that might be of independent interest, we establish a quantum adjunction theorem for Pultr functors between categories of relational structures, and we prove that the Dinur–Khot–Kindler–Minzer–Safra reduction, recently used for proving the 2-to-2 Games Theorem, is quantum complete.

We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on (i) the size of the shared quantum system used in the quantum strategy, and (ii) structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies.A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size.

Abstract. We introduce a relaxation for homomorphism problems that combines semidefinite programming with linear Diophantine equations and propose a framework for the analysis of its power based on the spectral theory of association schemes. We use this framework to establish an unconditional lower bound against the semidefinite programming + linear equations model by showing that the relaxation does not solve the approximate graph homomorphism problem and thus, in particular, the approximate graph coloring problem.

Abstract. We show that approximate graph coloring 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.

The 1 -in- 3 and N ot -A ll -E qual satisfiability problems for Boolean CNF formulas are two well-known NP -hard problems. In contrast, the promise 1 -in- 3 vs . N ot -A ll -E qual problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a rainbow-free structure and establish a complexity dichotomy for the resulting class of computational problems.

Information-processing tasks modelled by homomorphisms between relational structures can witness quantum advantage when entanglement is used as a computational resource. We prove that the occurrence of quantum advantage is determined by the same type of algebraic structure (known as a minion) that captures the polymorphism identities of CSPs and, thus, CSP complexity. We investigate the connection between the minion of quantum advantage and other known minions controlling CSP tractability and width. In this way, we make use of complexity results from the algebraic theory of CSPs to characterise the occurrence of quantum advantage in the case of graphs, and to obtain new necessary and sufficient conditions in the case of arbitrary relational structures.

The 1-in-3 and Not-All-Eqal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Eqal problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a rainbow-free structure, and establish a complexity dichotomy for the resulting class of computational problems.

We introduce a relaxation for homomorphism problems that combines semidefinite programming with linear Diophantine equations, and propose a framework for the analysis of its power based on the spectral theory of association schemes. We use this framework to establish an unconditional lower bound against the semidefinite programming + linear equations model, by showing that the relaxation does not solve the approximate graph homomorphism problem and thus, in particular, the approximate graph colouring problem.

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. * The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. This work was also supported by UKRI EP/X024431/1. † The full version of the paper can be accessed at https://arxiv.org/abs/2207.02277.

We show that approximate graph colouring is not solved by any level of the affine integer programming (AIP) hierarchy. To establish the result, we translate the problem of exhibiting a graph fooling a level of the AIP hierarchy into the problem of constructing a highly symmetric crystal tensor. In order to prove the existence of crystals in arbitrary dimension, we provide a combinatorial characterisation for realisable systems of tensors; i.e., sets of low-dimensional tensors that can be realised as the projections of a single high-dimensional tensor. * The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. This work was also supported by UKRI EP/X024431/1. † The full version of the paper can be accessed at https://arxiv.org/abs/2210.08293

We show that approximate graph colouring is not solved by constantly many levels of the lift-and-project hierarchy for the combined basic linear programming and affine integer programming relaxation. The proof involves a construction of tensors whose fixed-dimensional projections are equal up to reflection and satisfy a sparsity condition, which may be of independent interest.

Abstract. We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the [Formula: see text] algorithm of Brakensiek et al. [SIAM J. Comput., 49 (2020), pp. 1232--1248] and not by a reduction to tractable finite-domain CSPs.

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterisation of the power of CLAP in terms of a minion homomorphism. Using this characterisation, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP + AIP algorithm of Brakensiek and Guruswami [SODA'20] and not by a reduction to tractable finite-domain CSPs.