Semidefinite Programming and Linear Equations vs. Homomorphism Problems

被引：0
作者：
Ciardo, Lorenzo [1 ]
Zivny, Stanislav [1 ]
机构：
[1] Univ Oxford, Oxford, England
来源：
PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024 | 2024年
关键词：
approximate graph colouring; approximate graph homomorphism; semidefinite programming relaxations; affine integer programming relaxations; Diophantine equations; promise constraint satisfaction; CONSTRAINT SATISFACTION; ASSOCIATION SCHEMES; ALGEBRAIC STRUCTURE; CHROMATIC NUMBER; SHERALI-ADAMS; COMPLEXITY; HARDNESS; POWER; RELAXATIONS; SYMMETRY;
D O I：
10.1145/3618260.3649635
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：1935 / 1943
页数：9
相关论文
共 46 条
12345