VOLUME Twenty Eight
TITLE: "Groups and Computation II"
EDITORS: Larry Finkelstein, William M. Kantor
Published by the American Mathematical Society

Ordering Information

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.

• 1. Preface
• 2. Table of Contents

PREFACE

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.

TABLE OF CONTENTS

Index of Volumes

DIMACS Homepage