On the relative power of algebraic approximations of graph isomorphism
share
We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the invertible map tests (introduced by Dawar and Holm) and proof systems with algebraic rules, namely polynomial calculus, monomial calculus and 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.
READ FULL TEXT