The ACO Seminar (2015–2016)

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.