To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
The scientific program consisted of invited lectures and short research announcements, as well as informal discussions and software demonstrations. The four extended length talks (by C. C. Sims, J. Neubuser, E. M. Luks and L. Babai) laid out part of the groundwork for discussions of relationships between implementation and complexity questions; this was continued in further talks and in informal settings. The present Proceedings, which contain most, but not all, of the talks given at the Workshop, are dominated by papers amplifying these relationships. However, there were further subjects discussed in the Workshop and represented here: parallel algorithms for groups, computation in associative algebras, asymptotic behavior of permutation groups, studying finite groups using infinite reflection groups, combinatorial searching, computing with representations (including applications to statistics), and Cayley graphs as models for interconnection networks. Some of these subjects naturally led to practical computational questions. In fact, the difficulty encountered in attemping to separate or pigeon-hole the papers in this volume is indicative of the fact that there are no clear dividing lines between practical and theoretical aspects of the subject of the Workshop, nor between the needs of users and those more interested in the algorithms themselves.
It was our belief that a full discussion of implementation experiences would lead to a deeper understanding of the mathematical issues that underlie group computations, leading both to new algorithms and to improvements of existing ones. In order to provide some background for this, software provided by the participants was available during the entire Workshop; it was discussed in a number of talks, and one evening was devoted to informal software presentations. In addition, there was a panel discussion whose theme was "Problems whose current algorithmic solutions are, in practice, too time- or space-consuming." The panelists were selected for their broad experience in building software for group computation; the discussions provided insight into implementation problems and goals.
We are grateful for the assistance of our co-organizers, Daniel Gorenstein and Charles Sims. The possibility of arranging a Workshop arose accidentally during lunch with Danny, a mere thirteen months before the Workshop took place. His encouragement and enthusiasm helped us to overcome many of the usual difficulties encountered when organizing an international workshop. We also thank the staff at DIMACS for their efforts in helping the Workshop to function smoothly. Donna Harmon and Christine Thivierge of the American Mathematical Society provided invaluable assistance in the production of these Proceedings. Finally, we thank DIMACS, the National Science Foundation, the National Security Agency and Rutgers University for their financial support of the Workshop.
Foreword xi
Preface xiii
Workshop Program xv
Participants xvii
Computing Composition Series in Primitive Groups
Laszlo Babai, Eugene M. Luks, and Akos Seress 1
Computing Blocks of Imprimitivity for Small-Base Groups in
Nearly Linear Time 17
Robert Beals
Fast Fourier Transforms for Symmetric Groups
Michael Clausen and Ulrich Baum 27
From Hyperbolic Reflections to Finite Groups
J. H. Conway 41
Combinatorial Tools for Computational Group Theory
Gene Cooperman and Larry Finkelstein 53
Efficient Computation of Isotypic Projections
for the Symmetric Group 87
Persi Diaconis and Daniel Rockmore
Constructing Representations of Finite Groups
John D. Dixon 105
A Graphics System for Displaying Finite Quotients
of Finitely Presented Groups 113
Derek F. Holt and Sarah Rees
Random Remarks on Permutation Group Algorithms
William M. Kantor 127
Application of Group Theory to Combinatorial Searches
Clement W. H. Lam 133
Permutation Groups and Polynomial-Time Computation
Eugene M. Luks 139
Parallel Computation of Sylow Subgroups in Solvable Groups
Peter D. Mark 177
Computation with Matrix Groups over Finite Fields
Cheryl E. Praeger 189
Asymptotic Results for Permutation Groups
Laszlo Pyber 197
Computations in Associative Algebras
Lajos Ronyai 221
Cayley Graphs and Direct-Product Graphs
Arnold L. Rosenberg 245
Group Membership for Groups with Primitive Orbits
Namita Sarawagi, Gene Cooperman, and 253
Larry Finkelstein
PERM: A Program Computing Strong Generating Sets
Akos Seress and Ivan Weisz 269
Complexity Issues in Infinite Group Theory
Charles C. Sims 277
GRAPE: A System for Computing with Graphs and Groups
Leonard H. Soicher 287
Implications of Parallel Architectures for Permutation
Group Computations 293
Bryant W. York