Computational Algebra Seminar: Roney-Dougal -- Backtrack search problems in permutation groups

Speaker: Colva Roney-Dougal (St Andrews)
Title: Backtrack search problems in permutation groups
Time & Place: 2-3pm, Thursday 15 March, Carslaw 535

Abstract:
When computing with subgroups of a finite symmetric group Sym(n), we
generally seek algorithms whose worst-case running time is bounded by a
low-degree polynomial in n. However, there are a range of problems where no
such algorithms are known, and where the best current methods involve
algorithms whose running time may be much worse than this. I’ll give an
introduction to this class of problems, present results on various special
cases where we can recover polynomial running time, and briefly discuss some
ongoing work on computing normalisers in the full symmetric group. The new
material is joint work with Mun See Chang and Chris Jefferson at St Andrews.