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 proof systems with algebraic rules, namely \emph{ polynomial calculus}, \emph{ monomial calculus} and \emph{ Nullstellensatz calculus}. In the case of fields of characteristic zero, these variants are all essentially equivalent to the the Weisfeiler-Leman algorithms. In positive characteristic we show that the invertible map method can simulate the monomial calculus and identify a potential way to extend this to the monomial calculus.
Categories: cs.LO math.CO