Semidefinite Programming and Linear Equations vs. Homomorphism Problems
- 7 May 2025
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 54 (3) , 545-584
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.Keywords
All Related Versions
Funding Information
- UK Research and Innovation (EP/X024431/1)
This publication has 73 references indexed in Scilit:
- Computational Invariant Theory2015
- Improved Hardness of Approximating Chromatic Number2013
- Approximation Algorithms and Semidefinite Programming2012
- Algebraic Graph Theory2001
- Semidefinite Programs and Association SchemesComputing, 1999
- An exact duality theory for semidefinite programming and its complexity implicationsMathematical Programming, 1997
- Distance-Regular Graphs1989
- Current research on algebraic combinatoricsGraphs and Combinatorics, 1986
- Reducibility among Combinatorial Problems1972
- Zur Theorie der MatricesMathematische Annalen, 1907