Graph isomorphism: physical resources, optimization models, and algebraic characterizations
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 976 KB, PDF-dokument
In the (G, H)-isomorphism game, a verifier interacts with two non-communicating players (called provers), by privately sending each of them a random vertex from either G or H. The goal of the players is to convince the verifier that the graphs G and H are isomorphic. In recent work along with Atserias et al. (J Comb Theory Ser B 136:89–328, 2019) we showed that a verifier can be convinced that two non-isomorphic graphs are isomorphic, if the provers are allowed to share quantum resources. In this paper we model classical and quantum graph isomorphism by linear constraints over certain complicated convex cones, which we then relax to a pair of tractable convex models (semidefinite programs). Our main result is a complete algebraic characterization of the corresponding equivalence relations on graphs in terms of appropriate matrix algebras. Our techniques are an interesting mix of algebra, combinatorics, optimization, and quantum information.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Mathematical Programming |
Vol/bind | 205 |
Sider (fra-til) | 617–660 |
ISSN | 0025-5610 |
DOI | |
Status | Udgivet - 2024 |
Bibliografisk note
Funding Information:
Open access funding provided by Technical University of Denmark Funding was provided by Villum Fonden (Grant No. 10059).
Publisher Copyright:
© 2023, The Author(s).
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
ID: 366542779