Efficient algorithmic learning of the structure of permutation groups by examples

This paper discusses learning algorithms for ascertaining membership, inclusion, and equality in permutation groups. The main results are randomized learning algorithms which take a random generator set of a fixed group G≤Sn as input. We discuss randomized algorithms for learning the concepts of group membership, inclusion, and equality by representing the group in terms of its strong sequence of generators using random examples from G. We present O(n3 log n) time sequential learning algorithms for testing membership, inclusion and equality. The running time is expressed as a function of the size of the object set. (G≤Sn can have as many as n! elements.) Our bounds hold for all input groups. We also introduce limited parallelism, and our lower processor bounds make our algorithms more practical. Finally, we show that learning two-groups is in class NC by reducing the membership, inclusion, and inequality problems to solving linear systems over GF(2). We present an O(log3 n) time learning algorithm using n$+ω/ processors for learning two groups from examples (where n×n matrix product takes logarithmic time using n$+ω/ processors).

Duke Scholars

Author Salman Azhar Fuqua School of Business

Author John H. Reif Computer Science