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.