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.