Anuj Dawar

In this talk I will talk of families of equivalence relations that approximate graph isomorphism and are polynomialtime decidable. The WeisfeilerLehman 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 CaiFuererImmerman 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 WL method to algebras over finite fields. This is joint work with Bjarki Holm. 