AF: Small: Collaborative Research: Groups in Computer Science

AF：小型：协作研究：计算机科学小组

• 批准号: 1017182
• 负责人: Matthew Kahle
• 金额: $ 18.62万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017182&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Groups

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.

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