Laszlo Babai: Graph Isomorphism in Quasipolynomial Time
Tuesday, February 2, 2016 - 4:00pm to 5:00pm
Refreshments:
Light Refreshments at 3:50pm, 5th floor lounge Gates Tower
Location:
Stata Center Room 32 - 141
Speaker:
Laszlo Babai, Dept. Comp. Science and Mathematics, Univ. of Chicago
Seminar group:
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.