Relaxations of graph isomorphism

Speaker:

Newly appointed Associate Professor Laura Mancinska 

Title:

Relaxations of graph isomorphism

Abstract:

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. This leads us to notions of quantum and non-signaling graph isomorphism. In the second part of our investigation, we consider conic relaxations of GI.

For all of the considered relaxations we investigate whether they coincide with existing relations. For example, we were surprised to find that our notion of non-signaling isomorphism is equivalent to fractional isomorphism and doubly-nonnegative-isomorphism coincides with graph equivalence. We show that all of the introduced isomorphism relations form a strict hierarchy nested between GI and non-signalling isomorphism. The complexity of testing these relations ranges from linear time (non-signalling isomorphism) to undecidable (quantum isomorphism). The techniques and ideas employed span across quantum information, algebra, combinatorics, and complexity theory.

This is a joint work with Albert Atserias, Robert Šamal, David Roberson, Simone Severini, and Antonios Varvitsiotis.

Reception

There will be a reception on the 4th floor of the mathematics building afterwards.