Month: September 2015

Title: Computing canonical forms of graphs

Abstract: Determining the computational complexity of the problem of finding canonical representatives of graphs is a long-standing unresolved question.  This question is of fundamental interest in the theory of computing because of its close relationship with graph-isomorphism testing.

While the problem may be difficult in general, group-theoretic methods have enabled polynomial-time solutions for important classes of graphs, including graphs of bounded valence.  In practice, however, variants of backtrack search to find lexicographic leaders have long been accepted as quite effective; for example, the system nauty is the leader in this category.

In this talk, I will discuss theoretical limitations of the lexicographic-leader approach to finding canonical forms.  It turns out that this approach leads to NP-complete problems, even for very restricted classes of graphs for which there are simple polynomial-time solutions by group-theoretic methods.

Title: Tying different knots: problems with isomorphism in algebra

Abstract: In 1905 Max Dehn proved if you tie a knot by “over-under” you never end up with the same knot as when you tie it “under-over”.  His proof — still the only proof — hinged on a very delicate and typically difficult problem of computing isomorphisms in algebra.  By the 1950’s Adian and Rabin had proved the approach in general is undecidable — no computer can do it.

Yet, the uses for isomorphism are too profound to give up after undecidability. The decades that followed saw the founders of computational algebra – Cannon, Neubuser, and Sims – make substantial inroads on the problem.  Theoretical Computer Scientists Miller, Lipton-Zalcstein, and Tarjan framed the problem in the emerging complexity zoo with the curious realization that group isomorphism is in one form easier than graph isomorphism and in another form harder.

Today isomorphism in algebra is experiencing a renaissance.  Long-standing “hard cases” are crumbling with the discovery of new linear perspectives.  Old practical algorithms are being combined with new data structures to result in exponential improvements.  And the approaches grow by the month.  The vanguard of this exciting new wave are researchers at  Aachen, Auckland, Bucknell, Chicago, Colorado State, London, Santa Fe, and Sydney.

We will report on what we know, what we want to know, and give the reasons for all the recent attention. The talk will not assume a technical proficiency in mathematics or computation.