Abstract

An approximation scheme for graph ismorphism is a series of equivalence relations, each polynomial-time definable that, whose limit is graph isomorphism. The classic example of such a scheme is the family of Weisfeiler-Lehman equivalences. In this talk I describe a variation, and strengthening, of these based on invertible linear maps over finite vector spaces and suggest ways of analyzing them.

Video Recording