SMS scnews item created by Bill Unger at Mon 12 Mar 2018 1116
Type: Seminar
Distribution: World
Expiry: 16 Mar 2018
Calendar1: 15 Mar 2018 1400-1500
CalLoc1: Carslaw 535A
CalTitle1: Roney-Dougal -- Backtrack search problems in permutation groups
Auth: billu@laplace.maths.usyd.edu.au

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.