Graph Isomorphism: The emergence of the Johnson graphs

ACO Distinguished Lecture
Monday, January 9, 2017 - 16:30
1 hour (actually 50 minutes)
Klaus 1116
University of Chicago

This lecture is part of ACO25, a conference celebrating the 25th anniversary of the ACO Program. For more details about the conference please visit <a href="" title=""></a>

One of the fundamental computational problems in the complexity class NP on Karp's 1973 list, the Graph Isomorphism problem asks to decide whether or not two given graphs are isomorphic. While program packages exist that solve this problem remarkably efficiently in practice (McKay, Piperno, and others), for complexity theorists the problem has been notorious for its unresolved asymptotic worst-case complexity. In this talk we outline a key combinatorial ingredient of the speaker's recent algorithm for the problem. A divide-and-conquer approach requires efficient canonical partitioning of graphs and higher-order relational structures. We shall indicate why Johnson graphs are the sole obstructions to this approach. This talk will be purely combinatorial, no familiarity with group theory will be required.