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: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2025
|
| _version_ | 1824458999397875712 |
|---|---|
| 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 | 2025-02-19T04:34:49Z |
| format | Journal article |
| id | oxford-uuid:7547194d-e0a1-4fa3-8a02-907582765885 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:34:49Z |
| publishDate | 2025 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:7547194d-e0a1-4fa3-8a02-9075827658852025-01-22T15:18:21ZSemidefinite programming and linear equations vs. homomorphism problemsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7547194d-e0a1-4fa3-8a02-907582765885EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2025Ciardo, 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 |