Graph Isomorphism in Quasipolynomial Time: The emergence of the Johnson graphs

-
Laci Babai , University of Chicago
Fine Hall 314

Please note different day (Tuesday) and location (Fine 314).   Babai will give two talks at IAS Mon/Tue morning on his new Graph Isomorphism algorithm and will give the third (self contained combinatorial) part here.  This talk will give a brief outline of the algorithm, followed by technical details of the second combinatorial partitioning algorithm ("Split-or-Johnson" routine) required for the group theoretic recurrence. The technical material will be complementary to the IAS talks, so while attendance of the IAS lectures is not required for understanding this talk, for those who did attend the IAS talks, this lecture will provide details of the last remaining major ingredient.