Graph isomorphism in quasipolynomial time: the emergence of the Johnson graphs

Princeton University Discrete Mathematics Seminar
Topic:Graph isomorphism in quasipolynomial time: the emergence of the Johnson graphs
Speaker:László Babai
Affiliation:University of Chicago
Date:Tuesday, March 1
Time/Room:3:00pm - 4:20pm/Fine 314, Princeton University

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.