SMS scnews item created by donnelly at Tue 24 Mar 2015 1832
Type: Seminar
Distribution: World
Expiry: 7 Apr 2015
Calendar1: 26 Mar 2015 1500-1600
CalLoc1: Carslaw 535A
Auth: donnelly@seurat.maths.usyd.edu.au

Computational Algebra Seminar: Unger -- Recognising the giant permutation groups

Speaker : Bill Unger

Title : Recognizing the giant permutation groups

Abstract:

Given generators for a permutation group we want to quickly
decide if the group is giant, that is, alternating or symmetric in their
natural representation.

These groups are so much larger than other permutation groups of the
the same degree that we need to take care in dealing with them.

I will look at a Monte Carlo algorithm that recognises these groups
with very little random sampling. We get a practical algorithm that is
better than current methods in Magma, and is also asymptotically good.
The new algorithm solves knapsack problems, which in this case can be
kept small, and hence solved quickly.