"Proceedings of the DIMACS Workshop on Groups and Computation", L Finkelstein and W.M. Kantor, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 28, 1997, AMS, Providence, RI.

Preface

The Workshop “Groups and Computation” took place at DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science on the campus of Rutgers University , on June 7-10, 1995. This, and an earlier Workshop held on Oct 7-10, 1991, aimed at merging theory and practice within the broad area of computation with groups. The primary goal of the previous Workshop was to foster a dialogue between researchers studying the computational complexity of group algorithms and those engaged in the development of practical software. It was expected that this would lead to a deeper understanding of the mathematical issues underlying group computations, and such understanding would lead in turn to faster algorithms. Comments and subsequent work indicated that this goal had been achieved beyond our expectations. In particular, as a result of that Workshop, new collaborations formed to test the practicality of algorithms designed to meet the theoretical goal of faster asymptotic running times. Some of these have now been implemented and have been shown to have superior practical performance. The second Workshop was designed to reinforce the progress in these directions.

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 applications to signal processing and data analysis, computations with finitely presented groups, 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 matrix group 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 particularly evident when it came to research on algorithms for computing with matrix groups. 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 group algorithms. The Proceedings contains several papers along these lines. The remarkable progress that has been achieved so far makes extensive 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 matrix 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 Mathematical Society provided invaluable assistance 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.