On the relative power of algebraic approximations of graph isomorphism

Anuj Dawar, Danny Vagnozzi

We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the \emph{invertible map tests} (introduced by Dawar and Holm) and…