Research work · 1987

Permutation groups in NC

László Babai, Eugene M. Luks, Ákos Seress

ACM Symposium on Theory of Computing (STOC)

Abstract

We show that the basic problems of permutation group manipulation admit efficient parallel solutions. Given a permutation group G by a list of generators, we find a set of NC-efficient strong generators in NC. Using this, we show, that the following problems are in NC: membership in G; determining the order of G; finding the center of G; finding a composition series of G along with permutation representations of each composition factor. Moreover, given G, we are able to find the pointwise stabilizer of a set in NC. One consequence is that isomorphism of graphs with bounded multiplicity of eigenvalues is in NC.

Download PDF

DOI: 10.1145/28395.28439