DVP talk: James Wilson, September 29th 4pm in Olin 372


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.

Comments are closed.


Places I've Been

The following links are virtual breadcrumbs marking the 12 most recent pages you have visited in Bucknell.edu. If you want to remember a specific page forever click the pin in the top right corner and we will be sure not to replace it. Close this message.