- Series
- ACO Distinguished Lecture
- Time
- Tuesday, January 10, 2017 - 11:05am for 1 hour (actually 50 minutes)
- Location
- Klaus 1116
- Speaker
- Laszlo Babai – University of Chicago
- Organizer
- Robin Thomas
Please Note: This lecture is part of ACO25, a conference celebrating the 25th anniversary of the ACO Program. For more details about the conference please visit http://aco25.gatech.edu/
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.