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 aga...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2024
|
| _version_ | 1811141041557864448 |
|---|---|
| author | Ciardo, L Zivny, S |
| author_facet | Ciardo, L Zivny, S |
| author_sort | Ciardo, L |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T08:22:56Z |
| format | Conference item |
| id | oxford-uuid:3c08b158-2f96-4e2c-acfa-d1c303d47b56 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:31:34Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:3c08b158-2f96-4e2c-acfa-d1c303d47b562024-08-30T10:42:01ZSemidefinite programming and linear equations vs. homomorphism problemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:3c08b158-2f96-4e2c-acfa-d1c303d47b56EnglishSymplectic ElementsAssociation for Computing Machinery2024Ciardo, LZivny, SWe 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. |
| spellingShingle | Ciardo, L Zivny, S Semidefinite programming and linear equations vs. homomorphism problems |
| title | Semidefinite programming and linear equations vs. homomorphism problems |
| title_full | Semidefinite programming and linear equations vs. homomorphism problems |
| title_fullStr | Semidefinite programming and linear equations vs. homomorphism problems |
| title_full_unstemmed | Semidefinite programming and linear equations vs. homomorphism problems |
| title_short | Semidefinite programming and linear equations vs. homomorphism problems |
| title_sort | semidefinite programming and linear equations vs homomorphism problems |
| work_keys_str_mv | AT ciardol semidefiniteprogrammingandlinearequationsvshomomorphismproblems AT zivnys semidefiniteprogrammingandlinearequationsvshomomorphismproblems |