- Series
- ACO Distinguished Lecture
- Time
- Monday, January 9, 2017 - 4:30pm 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/
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.