Fall 2016

Approximating Graph Isomorphism through Linear Maps

Wednesday, November 9th, 2016 11:30 am12:00 pm

Add to Calendar

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.