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.
Funding Information
  • UK Research and Innovation (EP/X024431/1)