Semidefinite programming and linear equations vs. homomorphism problems

Conference item

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 colouring problem.

Files:: Ciardo_and_Zivny_2024_Semidefinite_programming_and.pdf

(Preview, Version of record, pdf, 270.2KB, Terms of use)

Publisher:: Association for Computing Machinery
Host title:: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)
Journal:: Proceedings of the 56th Annual ACM Symposium on Theory of Computing More from this journal
Pages:: 1935 - 1943
Publication date:: 2024-02-09
Acceptance date:: 2024-02-08
Event title:: 56th Annual ACM Symposium on Theory of Computing (STOC 2024)
Event location:: Vancouver, Canada
Event website:: http://acm-stoc.org/stoc2024/
Event start date:: 2024-06-24
Event end date:: 2024-06-28
DOI:: 10.1145/3618260.3649635
ISBN:: 979-8-4007-0383-6

Copyright holder:: Ciardo and Živný.
Notes:: This paper will be presented at the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), 24th-28th June 2024, Vancouver, Canada. This is the accepted manuscript version of the article. The final version will be available online from a forthcoming edition of the conference proceedings.

If you are the owner of this record, you can report an update to it here: Report update to this record