Algorithms, Combinatorics and Optimization Seminar Laszlo Babai
University of Chicago
Title: Graph isomorphism in quasipolynomial time

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

The first half of the talk will give an overview of the algorithm, outline the core group theoretic routine (“Local Certificates”), and sketch the aggregation of the local certificates.

The second half of the talk will outline the combinatorial partitioning algorithms (“Design Lemma” and “Split-or-Johnson”) required for the group-theoretic recurrence.

Elements of undergraduate-level group theory such as facility with the concepts of normal subgroups, quotient groups, homomorphisms, conjugacy, orbits of permutation groups will be assumed.

Helpful reading:

E.M. Luks : Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comp. Sys. Sci., 25:42--65, 1982.

Date: Friday, January 22, 2016
Time: 1:30 pm
Location: Gates 6115
Submitted by:  Bukh
Note: Joint ACO/CS THEORY Seminar (3 hours long) Note unusual day, time, location and duration.