Tractable Approximations of Graph Isomorphism

Anuj Dawar ( University of Cambridge )

In this talk I will talk of families of equivalence relations that approximate graph isomorphism and are polynomial-time decidable. The Weisfeiler-Lehman method provides one such family which has a large variety of equivalent characterisations emerging separately from algebra, combinatorics and logic, which I will review. It is known (by Cai-Fuerer-Immerman 1992) that no fixed level of the hierarchy exactly characterises isomorphism. This has recently inspired the definition of a new hierarchy of equivalences, which I will present, which can be seen as a strengthening of the W-L method to algebras over finite fields.

This is joint work with Bjarki Holm.