Collaborative Research: Groups in Computer Science

这个项目有三个主要目标：设计、分析和实现有效处理矩阵群的算法；开发分析这种算法所需的数学工具；以及应用群计算，包括理论和实践，以解决数学和计算机科学中的各种问题。这些领域最近取得了重大进展，这在相当大程度上要归功于PI及其合作者的研究；该项目确定并寻求新的攻击方向。群是对称性概念的数学公式，因此它们在数学和科学中无处不在。有限群及其相关Cayley图的算法有着广泛的应用，从群论问题到马尔可夫链的混合率问题，大型CPU阵列的互连网络的设计，图的同构问题(与计算机科学和化学文献相关)，基于群的密码学，以及构造具有高度对称性的图和设计。该提议的更广泛的影响主要是通过在GAP中实现新的算法。GAP是世界范围内的分布式、免费的计算机代数系统，它为群论、代数、图论、编码理论和设计理论的研究提供了一个计算环境，数百篇研究论文将GAP作为其中使用的工具。在本科抽象代数课程中使用GAP的需求也越来越大。该项目的主要主题是理论与实践的协同，对符号代数领域和计算理论都有好处。重点是设计和实现既能快速实现又能进行严格渐近分析的矩阵群算法。该项目开发了一种新的方法，结合并加强了几何和抽象结构(“黑箱”)技术这两种现有方法。该项目的另一个目标是进一步发展Neunh“Offer和第二个PI的最新数据结构，该数据结构将各种置换和矩阵群算法组合成一个连贯的系统。有限单群的元素阶数的统计研究一直是最近重要算法发展的关键；该项目通过母函数方法将这一研究扩展到群元素对的分布。此外，该项目包括群论、组合学和计算机科学中的问题，这些问题可能是新算法的设计和分析所必需的，或者可能由于从新机器获得的见解而变得可用。特别是，PI研究了本原置换群的最小基大小，对称群的Cayley图的直径，以及与图同构和布尔复杂性有关的问题，包括具有自同构群的传递群的布尔函数的参数和性质测试。

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.