Mathematically inclined Cube Hackers in the Boston area might find the
following seminar interesting. All I know about this is what I read here
in the abstract. (I'll bet its been a while since anyone on this list did
any serious thinking about the Cube as a permutation group...)
DATE: Thursday, May 28, 1987 TIME: Refreshments: 3:45PM LECTURE: 4:00PM PLACE: NE43-512A
PERMUTATION GROUPS IN NC
Mathematical Institute of the
Hungarian Academy of Sciences
Given a permutation group G on an n-element set A by a list of generators, we
present NC-algorithms (parallel algorithms using (log n)^c time and
n^c processors) for basic permutation group manipulation (membership
testing, order). These problems have been suggested by Cook and McKenzie to
be LOGSPACE-complete for P and therefore not in NC unless NC=P.
We shall outline previous work by Luks on the subject and focus on the
key problems left open by Luks' 1986 FOCS paper. In particular, we shall
discuss in detail, how to construct in NC any permutation from a given set of
generators of the symmetric group.
The presentation will be elementary, although the analysis of the
algorithms depends in several ways on consequences of the classification of
finite simple groups.
Our methods have sequential consequences as well. We obtain algorithms
for basic permutation group management with O(n^4(log n)^c) running
time, improving one order of magnitude from the best prevously known results
(Knuth, Babai, and Jerrum).
This is joint work with Laszlo Babai and Eugene M. Luks.
Host: Professor David Shmoys