Relaxations of graph isomorphism

DOI10.4230/LIPICS.ICALP.2017.76zbMATH Open1441.68190MaRDI QIDQ5111407FDOQ5111407

Authors: L. Mančinska, David Roberson, Robert Šámal, Simone Severini, A. Varvitsiotis 

Publication date: 27 May 2020

Recommendations

• Quantum and non-signalling graph isomorphisms
• Bigalois extensions and the graph isomorphism game
• The Morita theory of quantum graph isomorphisms
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• Nonlocal games and quantum permutation groups

zbMATH Keywords

semidefinite programmingquantum informationgraph isomorphism

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Applications of game theory (91A80) Semidefinite programming (90C22) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35)

Cited In (6)

• Fractional isomorphism of graphs
• Bisynchronous games and factorizable maps
• Quantum and non-signalling graph isomorphisms
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Title not available (Why is that?)
• Positively factorizable maps

This page was built for publication: Relaxations of graph isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111407)