Type: Seminar

Distribution: World

Expiry: 7 Apr 2015

Auth: donnelly@seurat.maths.usyd.edu.au

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.