Group theory and the Graph Isomorphism problem

Series: 
ACO Distinguished Lecture
Tuesday, January 10, 2017 - 11:05
1 hour (actually 50 minutes)
Location: 
Klaus 1116
,  
University of Chicago
Organizer: 

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="http://aco25.gatech.edu/" href="http://aco25.gatech.edu/">http://aco25.gatech.edu/</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.