Laszlo Babai: Graph Isomorphism in Quasipolynomial Time

Wednesday, February 3, 2016 - 5:00pm to 8:00pm
Location: 
Harvard, Pierce 301
Speaker: 
Laszlo Babai, Dept. Comp. Science and Mathematics, Univ. of Chicago
Seminar group: 
Harvard/MIT/MSR Reading Group

Abstract:  The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools.

The first part of the talk will give an overview of the algorithm, discuss the core group theoretic routine ("Local Certificates") in detail, and sketch the aggregation of the local certificates.

After a break, we shall discuss the combinatorial partitioning techniques ("Design Lemma" and "Split-or-Johnson") required for the group-theoretic recurrence.

Elements of undergraduate-level group theory such as facility with the concepts involved in the Jordan--Holder Theorem and basic concepts of permutation groups (such as orbits) will be assumed.

Helpful reading:

Eugene M. Luks:

Isomorphism of graphs of bounded valence can be tested in polynomial time. JCSS 25(1) (1982) 42--65.

Please note that the preceding day, Tuesday, February 2, 4:05-5:00pm, I will present an outline of the algorithm at the MIT Theory Colloquium. Attendance of that talk is not a prerequisite for this seminar, but it may be helpful.