Dear quanta,
David Rosenbaum will be speaking tomorrow at noon in the math
department (specifically the pure math grad student seminar) about
algorithms for group isomorphism. The talk is 99% classical, but
nevertheless may be of interest for quantum people because of the
overlap between computational group theory and quantum computing. It
may also be of interest to people who like pizza, because there will
be pizza there.
Location: 4-153
Title: Faster Algorithms for Group Isomorphism
Abstract:
In the group isomorphism problem, we are given two finite groups G and
H specified by their multiplication tables and must decide if they are
isomorphic. The n^(log n)$ barrier for group isomorphism has
withstood all attacks --- even for the special cases of p-groups and
solvable groups --- ever since the n^(log n + O(1))
generator-enumeration algorithm. In this work, we present the first
significant improvement over n^(log n) by formulating group
isomorphism as a collision problem. Using a new technique called
bidirectional collision detection, we show an n^((1 / 2) log n + O(1))
time algorithm for testing isomorphism of general groups.
We also show a deterministic n^((1 / 4) log n + O(1)) Turing reduction
from group isomorphism to composition-series isomorphism. By
combining our reduction with an n^(O(p / log p)) algorithm for p-group
composition-series isomorphism, we obtain an n^((1 / 4) log n + O(1))
algorithm for p-group isomorphism. We then generalize our techniques
from p-groups using Sylow bases to derive an n^((1 / 4) log n + O(log
n / log log n)) algorithm for solvable-group isomorphism.
Note: This work is based partially on David's paper 1205.0642, and
partially on some new unpublished work.
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip