Collaborative Research: Groups in Computer Science

点击翻译按钮获取中文摘要

This project has three main goals: the design, analysis, and implementation of algorithms for efficiently processing matrix groups; the development of the mathematical tools required for the analysis of such algorithms; and the application of group computations, both theoretical and practical, to solve various problems in mathematics and computer science. These areas have seen major recent progress, to a considerable degree due to research by the PIs and their collaborators; the project identifies and pursues new directions of attack.Groups are the mathematical formulation of the notion of symmetry, and so they are ubiquitous in mathematics and the sciences. Algorithms for finite groups and their associated Cayley graphs have a wide range of applications, from problems of group theory to the mixing rate of Markov chains, the design of interconnection networks for large interacting arrays of CPU's, the graph isomorphism problem (of relevance to computer science and to chemical documentation), group-based cryptography, and the construction of graphs and designs with a high degree of symmetry.The broader impact of the proposal is primarily through the implementations of the new algorithms in GAP. GAP is world-wide distributed, free computer algebra system that provides a computing environment for research in group theory, algebra, graph theory, coding theory, and design theory, and hundreds of research papers cite GAP as a tool used in them. There is also an increasing demand to use GAP in undergraduate abstract algebra courses.The principal theme of the project is the synergy between the theoretical and the practical, benefitting both the field of Symbolic Algebra and the Theory of Computing. The focus is on the design and implementation of matrix group algorithms that are both fast in practice and admit rigorous asymptotic analysis. The project develops a new methodology which combines and enhances the two existing approaches, the geometric and the abstract structural (``black-box'') techniques. Another goal of the project is the further development of a recent data structure by Neunh\"offer and the second PI that combines the various permutation and matrix group algorithms into a coherent system.Statistical study of the element-orders of finite simple groups has been a key to recent significant algorithmic developments; the project extends this line of study to the distributions of pairs of groups elements via generating function methods.Further, the project includes problems in group theory, combinatorics, and computer science that may either be necessary for the design and analysis of the new algorithms, or may become accessible due to insights obtained from the new machinery. In particular, the PIs study the minimum base size of primitive permutation groups, the diameter of Cayley graphs of the symmetric groups, and problems related to graph isomorphism and Boolean complexity, including ``property testing'' and parameters of Boolean functions with a transitive group of automorphisms.