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.
Title: GRAM-SCHMIDT TYPE ALGORITHMS