Graph isomorphism: physical resources, optimization models, and algebraic characterizations

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Graph isomorphism : physical resources, optimization models, and algebraic characterizations. / Mančinska, Laura; Roberson, David E.; Varvitsiotis, Antonios.

In: Mathematical Programming, 2024.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Mančinska, L, Roberson, DE & Varvitsiotis, A 2024, 'Graph isomorphism: physical resources, optimization models, and algebraic characterizations', Mathematical Programming. https://doi.org/10.1007/s10107-023-01989-7

APA

Mančinska, L., Roberson, D. E., & Varvitsiotis, A. (2024). Graph isomorphism: physical resources, optimization models, and algebraic characterizations. Mathematical Programming. https://doi.org/10.1007/s10107-023-01989-7

Vancouver

Mančinska L, Roberson DE, Varvitsiotis A. Graph isomorphism: physical resources, optimization models, and algebraic characterizations. Mathematical Programming. 2024. https://doi.org/10.1007/s10107-023-01989-7

Author

Mančinska, Laura ; Roberson, David E. ; Varvitsiotis, Antonios. / Graph isomorphism : physical resources, optimization models, and algebraic characterizations. In: Mathematical Programming. 2024.

Bibtex

@article{5c27183163fe4612b68e67eaf6d83c60,
title = "Graph isomorphism: physical resources, optimization models, and algebraic characterizations",
abstract = "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.",
author = "Laura Man{\v c}inska and Roberson, {David E.} and Antonios Varvitsiotis",
note = "Publisher Copyright: {\textcopyright} 2023, The Author(s).",
year = "2024",
doi = "10.1007/s10107-023-01989-7",
language = "English",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",

}

RIS

TY - JOUR

T1 - Graph isomorphism

T2 - physical resources, optimization models, and algebraic characterizations

AU - Mančinska, Laura

AU - Roberson, David E.

AU - Varvitsiotis, Antonios

N1 - Publisher Copyright: © 2023, The Author(s).

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85164818975&partnerID=8YFLogxK

U2 - 10.1007/s10107-023-01989-7

DO - 10.1007/s10107-023-01989-7

M3 - Journal article

AN - SCOPUS:85164818975

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -

ID: 366542779