Collaborative Research: Groups in Computer Science

合作研究：计算机科学小组

• 批准号: 0830534
• 负责人: Akos Seress
• 金额: $ 13.45万
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830534&HistoricalAwards=false
• 关键词: Collaborative; Research; Groups; 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.

该项目有三个主要目标：设计，分析和实现有效处理矩阵群的算法;开发分析此类算法所需的数学工具;以及理论和实践中的群计算应用，以解决数学和计算机科学中的各种问题。 这些领域最近取得了重大进展，在很大程度上归功于PI及其合作者的研究;该项目确定并追求新的攻击方向。群是对称性概念的数学表述，因此它们在数学和科学中无处不在。有限群及其相关Cayley图的算法有着广泛的应用，从群论问题到马尔可夫链的混合率，大型交互CPU阵列的互连网络设计，图同构问题，等等。（与计算机科学和化学文献相关），基于组的密码学，以及具有高度对称性的图形和设计的构造。该提案的更广泛影响主要是通过在GAP中实现新算法。GAP是一个全球性的分布式、免费的计算机代数系统，它为群论、代数、图论、编码理论和设计理论的研究提供了一个计算环境，数百篇研究论文引用GAP作为其中使用的工具。 在本科抽象代数课程中使用GAP的需求也越来越多。该项目的主题是理论与实践之间的协同作用，使符号代数和计算理论领域受益。重点是矩阵组算法的设计和实现，在实践中都是快速的，并承认严格的渐近分析。该项目开发了一种新的方法，结合并加强了两种现有的方法，几何和抽象结构（"黑盒“）技术。 该项目的另一个目标是进一步发展Neunh offer和第二个PI最近的数据结构，将各种置换和矩阵群算法结合到一个连贯的系统中。该项目通过生成函数方法将这一研究方向扩展到群元素对的分布。2此外，该项目还包括群论，组合学，和计算机科学，这可能是必要的设计和分析的新算法，或可能成为访问由于见解获得的新机制。 特别是，PI研究原始置换群的最小基大小，对称群的凯莱图的直径，以及与图同构和布尔复杂性相关的问题，包括“属性测试”和具有自同构传递群的布尔函数的参数。