ylfink@water.UUCP (ylfink) (10/20/86)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY OF ALGORITHMS
(Joint with C&O)
- Tuesday, October 21, 1986.
Dr. Laszlo Babai of Eotvos University, Hungary will
speak on ``Parallel algorithms for permutation
groups''.
TIME: 1:30 PM
ROOM: MC 5158
ABSTRACT
We report on recent joint work with Akos Seress (Hun-
garian Academy of Sciences). Given a permutation group
by a list of generators, we show that testing member-
ship, determining order, normal closure in another
group, kernel of action, composition series are in NC.
The results involve the following ingredients:
1. The augmented structure forest, the associated sem-
isimple structure and the ``noncommutative linear
algebra'' introduced by Luks (FOCS 1986, Toronto).
2. Previous work by Cook and McKenzie for the abelian
and by Luks and McKenzie for the solvable case.
(Randomization eliminated by Mulmuley's recent
result.)
3. Luks' sequential algorithm to find composition
series (to appear in Combinatorica).
4. A parallel speedup of Sims' sifting method. (We
have just learned that this had independently been
found by Luks and around the same time.)
5. A novel NC-efficient way of constructing strong
generators for the giants (symmetric and alternat-
ing groups).
October 20, 1986
- 2 -
6. A combinatorial algorithm involving hybrid
Hamming-Johnson schemes to reduce large primitive
groups other than the giants.
The analysis of the algorithm makes heavy use of
several consequences of the Classification of Finite
Simple Groups.
The talk will concentrate on #5, accessible without
knowledge of group theory.
October 20, 1986