Quantum-inspired relaxations of graph isomorphism
During the last 50 years, the study of equivalence for relational structures has developed into a vast theory embracing combinatorics, optimization, algebra, and mathematical logic. In this context, graph isomorphism (GI) and its hierarchy of relaxations constitute a central topic, not only for its elusive complexity, but also for its mathematical richness. We develop two frameworks which not only provide a new and unifying perspective of well-known relaxations of GI such as fractional isomorphism and graph equivalence but also allow us to define new relaxations of GI. For instance, using our nonlocal games-based framework we can introduce and study variants of GI inspired by different physical postulates which leads us to notions of quantum and non-signaling graph isomorphism.
This is a joint work with A. Atserias, D.E. Roberson, R. Šamal, S. Severini and A. Varvitsiotis.