Group theory and the Graph Isomorphism problem

ACO Distinguished Lecture
Tuesday, January 10, 2017 - 11:05
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&nbsp;<a title="" href=""></a>

In this talk we outline the core group theoretic routine, the "Local Certificates" algorithm, underlying the new Graph Isomorphism test. The basic strategy follows Luks's group-theoretic divide-and-conquer approach (1980). We address the bottleneck of Luks's technique via local-global interaction based on a new group theoretic lemma. Undergraduate-level familiarity with the basic concept of group theory (homomorphism, kernel, quotient group, permutation groups) will be assumed.