Article Source

• Graph isomorphism in quasipolynomial time

Graph Isomorphism in Quasipolynomial Time

• Computer Science/Discrete Mathematics Seminar I
• Topic: Graph isomorphism in quasipolynomial time I
• Speaker: László Babai
• Date: Monday, February 29, 2016

Abstract

The algorithm indicated in the title builds on Luks’s classical framework and introduces new group theoretic and combinatorial tools. In the first talk we outline the algorithm and state the core group theoretic and algorithmic ingredients. Some of the technical details will be given in the second talk, with a focus on the core group theoretic routine (“Local Certificates”) and the aggregation of the the local certificates. Time permitting, we also discuss one of the combinatorial partitioning algorithms (“Design lemma”). Elements of undergraduate-level group theory such as facility with the concepts involved in the Jordan–Holder theorem will be assumed. The paper is available at arXiv:1512.03547. Helpful reading: Eugene M. Luks: Isomorphism of graphs of bounded valence can be tested in polynomial time. JCSS 25(1) (1982) 42–65.