Tractable Approximations of Graph Isomorphism
Anuj Dawar ( University of Cambridge )
- 16:00 30th May 2014 ( week 5, Trinity Term 2014 )Room 278, Oxford e-Research Centre, 7 Keble Road
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.