2
[2311.00882] Semidefinite programming and linear equations vs. homomorphism prob...
source link: https://arxiv.org/abs/2311.00882
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Computational Complexity
[Submitted on 1 Nov 2023 (v1), last revised 17 Nov 2023 (this version, v2)]
Semidefinite programming and linear equations vs. homomorphism 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.
| Subjects: | Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC) |
| Cite as: | arXiv:2311.00882 [cs.CC] |
| (or arXiv:2311.00882v2 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2311.00882 |
Submission history
From: Stanislav Živný [view email][v1] Wed, 1 Nov 2023 22:15:19 UTC (70 KB)
[v2] Fri, 17 Nov 2023 05:02:40 UTC (70 KB)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK