AF: Small: Collaborative Research: Groups in Computer Science

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

The project continues the study of interconnections between group theory and the theory and practice of computation. The major objectives are (1) the design, analysis, and implementation of algorithms for computations with finite groups; (2) the development of mathematical tools required for the design and analysis of such algorithms; (3) the study of current bottlenecks in the graph isomorphism problem, a major open problem in the theory of computing; and (4) the computationally motivated study of discrete structures involving the group concept. The project will build on the PIs recent results of breaking quarter-century old bottlenecks in the areas of matrix group computation and on the graph isomorphism problem. A principal theme of the project is the synergy between the theoretical and practical, benefitting both the field of symbolic algebra and the theory of computing through the design and implementation of algorithms that are both fast in practice and admit rigorous complexity analysis. The project methodology in the area of matrix computations will combine elements of the two existing approaches, the geometric and abstract structural ("black-box") frameworks. The project also includes related problems in group theory, combinatorics, and computer science, connected through the algorithmic study of objects involving the group concept. In particular, a combination of such tools will be required for a renewed study of the bottlenecks that have blocked progress on the graph isomorphism problem and the related coset intersection problem in permutation groups. The PIs will also study of parameters of Boolean functions subject to symmetry conditions, including the complexity of property testing; and the Abelian Sandpile Model which connects a number of fields, including statistical mechanics, algebraic graph theory, discrete dynamical systems, algorithms, and complexity in the study of a certain commutative monoid and group.Groups are the mathematical formulation of symmetry, ubiquitous in mathematics and the sciences. Algorithms for finite groups and their associated Cayley graphs have a wide range of applications, from group theory to statistics, network design, the graph isomorphism problem (of relevance to computer science and chemical documentation), cryptography, and the construction of objects with high symmetry. The broader impact of the project is primarily through the implementation of new algorithms in GAP, a leading, open access computer algebra system that provides computing environment for research in group theory, algebra, graph theory, coding theory, and design theory. GAP development also represents a significant contribution to education as there is an increasing demand to use GAP in undergraduate abstract algebra courses.