Laszlo Babai: Graph Isomorphism in Quasipolynomial Time

Tuesday, February 2, 2016 - 4:00pm to 5:00pm
Light Refreshments at 3:50pm, 5th floor lounge Gates Tower
Stata Center Room 32 - 141
Laszlo Babai, Dept. Comp. Science and Mathematics, Univ. of Chicago
Abstract:  The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools.  

We outline the algorithm, with a focus on the core group theoretic routine ("Local Certificates").

Elements of undergraduate-level group theory such as facility with the concepts involved in the Jordan--Holder theorem will be assumed.

An in-depth discussion of the technical details will follow at a subsequent Harvard/MIT/MSR Theory Reading Group at Harvard (Pierce 301) on Wednesday, February 3, 2016, 5:00 - 8:00pm.
Helpful reading: Eugene M. Luks: Isomorphism of graphs of bounded valence can be tested in polynomial time.
 JCSS 25(1) (1982) 42--65.