{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T08:25:39Z","timestamp":1769761539178,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["10059"],"award-info":[{"award-number":["10059"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the (<jats:italic>G<\/jats:italic>,\u00a0<jats:italic>H<\/jats:italic>)-isomorphism game, a verifier interacts with two non-communicating players (called provers), by privately sending each of them a random vertex from either <jats:italic>G<\/jats:italic> or <jats:italic>H<\/jats:italic>. The goal of the players is to convince the verifier that the graphs <jats:italic>G<\/jats:italic> and <jats:italic>H<\/jats:italic> are isomorphic. In recent work along with Atserias et al. (J Comb Theory Ser B 136:89\u2013328, 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.\n<\/jats:p>","DOI":"10.1007\/s10107-023-01989-7","type":"journal-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T10:02:06Z","timestamp":1689328926000},"page":"617-660","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Graph isomorphism: physical resources, optimization models, and algebraic characterizations"],"prefix":"10.1007","volume":"205","author":[{"given":"Laura","family":"Man\u010dinska","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4463-8095","authenticated-orcid":false,"given":"David E.","family":"Roberson","sequence":"additional","affiliation":[]},{"given":"Antonios","family":"Varvitsiotis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"1989_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.jctb.2018.11.002","volume":"136","author":"A Atserias","year":"2019","unstructured":"Atserias, A., Man\u010dinska, L., Roberson, D.E., \u0160\u00e1mal, R., Varvitsiotis, A.: Quantum and non-signalling graph isomorphisms. J. Comb. Theory Ser. B 136, 89\u2013328 (2019)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1989_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74341-2","volume-title":"Distance-Regular Graphs","author":"AE Brouwer","year":"1989","unstructured":"Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin (1989)"},{"key":"1989_CR3","volume-title":"Spectra of Graphs","author":"AE Brouwer","year":"2011","unstructured":"Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, Berlin (2011)"},{"key":"1989_CR4","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/088","volume-title":"C*-Algebras and Finite-Dimensional Approximations","author":"NP Brown","year":"2008","unstructured":"Brown, N.P., Ozawa, N.: C*-Algebras and Finite-Dimensional Approximations. American Mathematical Society, London (2008)"},{"key":"1989_CR5","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s10107-008-0223-z","volume":"120","author":"S Burer","year":"2009","unstructured":"Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479\u2013495 (2009)","journal-title":"Math. Program."},{"issue":"3","key":"1989_CR6","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0024-3795(75)90075-0","volume":"10","author":"M-D Choi","year":"1975","unstructured":"Choi, M.-D.: Completely positive linear maps on complex matrices. Linear Algebra Appl. 10(3), 285\u2013290 (1975)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"1989_CR7","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E de Klerk","year":"2002","unstructured":"de Klerk, E., Pasechnik, D.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1989_CR8","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10107-008-0233-x","volume":"121","author":"I Dukanovic","year":"2010","unstructured":"Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the stability and the chromatic numbers. Math. Program. 121(2), 249\u2013268 (2010)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1989_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0166-218X(89)90047-4","volume":"25","author":"S Friedland","year":"1989","unstructured":"Friedland, S.: Coherent algebras and the graph isomorphism problem. Discrete Appl. Math. 25(1\u20132), 73\u201398 (1989)","journal-title":"Discrete Appl. Math."},{"key":"1989_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22015-9","volume-title":"Approximation Algorithms and Semidefinite Programming","author":"B G\u00e4rtner","year":"2012","unstructured":"G\u00e4rtner, B., Matousek, J.: Approximation Algorithms and Semidefinite Programming. Springer, Berlin (2012)"},{"key":"1989_CR11","unstructured":"Gijben, L.: On approximations, complexity, and applications for copositive programming. Ph.D. thesis, University of Groningen (2015)"},{"issue":"1","key":"1989_CR12","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1080\/00029890.1963.11990038","volume":"70","author":"AJ Hoffman","year":"1963","unstructured":"Hoffman, A.J.: On the polynomial of a graph. Am. Math. Mon. 70(1), 30\u201336 (1963)","journal-title":"Am. Math. Mon."},{"key":"1989_CR13","volume-title":"Handbook of Product Graphs","author":"W Imrich","year":"2011","unstructured":"Imrich, W., Hammack, R.H., Klav\u017ear, S.: Handbook of Product Graphs. CRC Press, Boca Raton (2011)"},{"key":"1989_CR14","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/990524.990529","volume":"10","author":"D Kozen","year":"1978","unstructured":"Kozen, D.: A clique problem equivalent to graph isomorphism. ACM SIGACT News 10, 50\u201352 (1978)","journal-title":"ACM SIGACT News"},{"key":"1989_CR15","doi-asserted-by":"publisher","DOI":"10.1142\/p665","volume-title":"Moments, Positive Polynomials and Their Applications","author":"JB Lasserre","year":"2009","unstructured":"Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. World Scientific, Singapore (2009)"},{"issue":"4","key":"1989_CR16","doi-asserted-by":"publisher","first-page":"2461","DOI":"10.1137\/14097865X","volume":"25","author":"M Laurent","year":"2015","unstructured":"Laurent, M., Piovesan, T.: Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. SIAM J. Optim. 25(4), 2461\u20132493 (2015)","journal-title":"SIAM J. Optim."},{"key":"1989_CR17","unstructured":"Man\u010dinska, L., Roberson, D.E.: Note on the correspondence between quantum correlations and the completely positive semidefinite cone (2014). http:\/\/quantuminfo.quantumlah.org\/memberpages\/laura\/corr.pdf"},{"key":"1989_CR18","doi-asserted-by":"crossref","unstructured":"Man\u010dinska, L., Roberson, D.E.: Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs (2019). arXiv:1910.06958","DOI":"10.1109\/FOCS46700.2020.00067"},{"key":"1989_CR19","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)"},{"key":"1989_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.laa.2016.02.019","volume":"497","author":"CM Ortiz","year":"2016","unstructured":"Ortiz, C.M., Paulsen, V.I.: Quantum graph homomorphisms via operator systems. Linear Algebra Appl. 497, 23\u201343 (2016)","journal-title":"Linear Algebra Appl."},{"key":"1989_CR21","unstructured":"Roberson, D.E.: Variations on a theme: graph homomorphisms. Ph.D. thesis, University of Waterloo (2013)"},{"issue":"4","key":"1989_CR22","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s10801-016-0665-y","volume":"43","author":"DE Roberson","year":"2016","unstructured":"Roberson, D.E.: Conic formulations of graph homomorphisms. J. Algebr. Combin. 43(4), 877\u2013913 (2016)","journal-title":"J. Algebr. Combin."},{"key":"1989_CR23","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A Schrijver","year":"1979","unstructured":"Schrijver, A.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Theory 25, 425\u2013429 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20132","key":"1989_CR24","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s10107-016-1049-8","volume":"162","author":"J Sikora","year":"2017","unstructured":"Sikora, J., Varvitsiotis, A.: Linear conic formulations for two-party correlations and values of nonlocal games. Math. Program. 162(1\u20132), 431\u2013463 (2017)","journal-title":"Math. Program."},{"key":"1989_CR25","doi-asserted-by":"crossref","unstructured":"Slofstra, W.: The set of quantum correlations is not closed. In: Forum of Mathematics, Pi, vol. 7 (2019)","DOI":"10.1017\/fmp.2018.3"},{"key":"1989_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/9781316848142","volume-title":"The Theory of Quantum Information","author":"J Watrous","year":"2018","unstructured":"Watrous, J.: The Theory of Quantum Information. Cambridge University Press, Cambridge (2018)"},{"key":"1989_CR27","doi-asserted-by":"crossref","unstructured":"Weisfeiler, B.: On construction and identification of graphs, volume 558 of Lecture Notes in Mathematics. Springer (1976). With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler","DOI":"10.1007\/BFb0089374"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01989-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01989-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01989-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T14:17:11Z","timestamp":1712413031000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01989-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,14]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1989"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01989-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,14]]},"assertion":[{"value":"23 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}