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 research announcements, as well as informal discussions and software demonstrations. The eight extended talks (by L. Babai, B. Eick, C. Leedham-Green, J. Leon, C. Miller, C. Praeger and A. Niemeyer, D. Rockmore, and M. Schonert) discussed randomization, permutation groups, matrix groups, software systems, fast Fourier transforms and their applicaitons to signal processing and data analysis, computations with finitely presented goups, as well as implementation and complexity questions. These topics were also discussed further talks, as were additional ones such as group-theoretic computation with graphs, algorithms for permutation groups, properties of simple groups, and parallel architectures for matix goup computation. As in the previous Workshop, speakers ranged from established researchers to graduate students. The present Proceedings contains papers base on most, but not all, of their talks.
Software provided by the participants was available during the entire workshop and was discussed in a number of talks. One evening was devoted to informal software presentations using various systems, including numerous demonstrations by participants using GAP or Magma. In addition, there was a panel discussion whose theme was "Problems whose current algorithmic solutions are, in practice either too time- or space-consuming". The panelists (G. Cooperman, G. Havas, J. Leon, J. Neubuser, M. Schonert and L. Soicher) were selected for their broad experience in building software for group computation.
What was most striking throughout the Workshop was the convergence of theory and practice begun at the first Workshop. Almost every talk concerning practical algorithms mentioned complexity issues; almost every talk focused on complexity mentioned practical considerations. This was particulary evident when it came to research on algorithms for computing with matrix goups. In contrast with the situation for permutation groups, finite matrix groups are too "large", from both a practical and a theoretical standpoint. As a result, very few computational problems for matrix groups have polynomial-time solutions (this is true even for simple-sounding problems such as finding the order of a matrix group). Particularly fascinating are the mathematical issues that have emerged as part of the search for reasonably efficient matrix goup algorithms. The Proceedings contains several papers along these lines. The remarkable progress that has been achieved so far makes extenxive use of the classification of finite simple groups, of randomized methods, and of polynomial computation using classical Symbolic Algebra methods. This progress could not have been predicted following the first DIMACS Workshop, which was dominated by permutation groups rather than matirx groups.
The first DIMACS Workshop came into being due to the formidable efforts of Danny Gorenstein, and hence the second one also owes much to him. We are grateful for the assistance of our co-organizer Charles Sims, and to the DIMACS staff for helping the workshop to function smoothly. Christine Thierviege of the American Mathemtaical Society provided invaluable assisance in the production of this Proceedings. Finally, we would like to thank DIMACS, the National Science Foundation, the National Security Agency and Rutgers University for their financial support of the workshop.
Larry Finkelstein
Foreward | ix |
Preface | xi |
Workshop Program | xiii |
Participants | xv |
Randomization in group algorithms: Conceptual questions
Laszlo Babai |
1 |
Experimenting and computing with infinite groups
Gilbert Baumslag, Charles F. Miller III |
19 |
Towards polynomial time algorithms for matrix groups
Robert Beals |
31 |
Calculating the order of an invertible matrix
Frank Celler, C.R. Leedham-Green |
55 |
A non-constructive recognition algorithm for the special
linear and other classical groups
Frank Celler, C.R. Leedham-Green |
61 |
GAP/MPI: Facilitating parallelism
Gene Cooperman |
69 |
Constructive recognition of a black box group isomorphic to GL9n,2)
Gene Cooperman, Larry Finkelstein, Steve Linton |
85 |
Special presentations for the finite soluble groups and computing
(pre-) Frattini subgroups
Bettina Eick |
101 |
Algorithms for group actions applied to graph generation
Thomas Gruner, Reinhard Laue, Markus Meringer |
113 |
Partitions, refinements, and permutation group computation
Jeffrey S. Leon |
123 |
A polycyclic quotient algorithm
Eddie H. Lo |
159 |
Computing the Fitting subgoup and solvable radical for small-base
permutation groups in nearly linear time
Eugene M. Luks, Akos Seress |
169 |
Generalized FFT's- A survey of some recent results
David K. Maslen, Daniel M. Rockmore |
183 |
The complixity of McKay's canonical labeling algorithm
Takunari Miyazaki |
239 |
On nearly linear time algorithms for Sylow subgoups of small base
permutation groups
Prabhav Morje |
257 |
Implementing a recognition algorithm for classical groups
Alice C. Niemeyer, Cheryl E. Praeger |
273 |
Algorithms for polycyclic-by-finite matrix groups
Gretchen Ostheimer |
297 |
Asymptotic results for simple groups and some applications
Laszlo Pyber |
309 |
Some applications of generalized FFT's
Daniel N. Rockmore |
329 |
Computing permutation representations for matrix groups in parallel
environments
Michael Tselman |
371 |