AF: Small: Collaborative Research: Groups in Computer Science

该项目继续研究群论与计算的理论和实践之间的相互联系。主要目标是(1)有限群计算算法的设计、分析和实现；(2)设计和分析这类算法所需的数学工具的开发；(3)研究当前图同构问题中的瓶颈，这是计算理论中的一个主要开放问题；以及(4)涉及群概念的计算驱动的离散结构的研究。该项目将建立在PIS的最新成果基础上，这些成果打破了矩阵群计算领域长达四分之一个世纪的瓶颈，并基于图形同构问题。该项目的一个主要主题是理论和实践之间的协同，通过设计和实现既在实践中快速又允许进行严格的复杂性分析的算法，使符号代数领域和计算理论都受益。矩阵计算领域的项目方法将结合几何和抽象结构(“黑箱”)框架这两种现有方法的要素。该项目还包括群论、组合学和计算机科学中的相关问题，通过对涉及群概念的对象的算法研究而联系在一起。特别是，需要这些工具的组合来重新研究阻碍图同构问题和置换群中相关陪集相交问题进展的瓶颈。PI还将研究受对称条件约束的布尔函数的参数，包括性质测试的复杂性；以及阿贝尔沙堆模型，该模型连接了多个领域，包括统计力学、代数图论、离散动力系统、算法以及研究特定交换么半群和群的复杂性。群是对称的数学公式，在数学和科学中普遍存在。有限群及其相关Cayley图的算法有着广泛的应用，从群论到统计学、网络设计、图同构问题(与计算机科学和化学文献相关)、密码学以及构造具有高度对称性的对象。该项目的更广泛影响主要是通过在GAP中实施新算法，GAP是一个领先的、开放访问的计算机代数系统，为群论、代数、图论、编码理论和设计理论的研究提供计算环境。GAP的发展也代表着对教育的重大贡献，因为在本科抽象代数课程中使用GAP的需求越来越大。

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.