AF: Small: Collaborative Research: Groups in Computer Science

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

• 批准号: 1017781
• 负责人: Laszlo Babai
• 金额: $ 31.38万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017781&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）基于计算的离散结构群研究。 该项目将建立在PI最近的成果，打破了四分之一世纪的瓶颈领域的矩阵组计算和图同构问题。 该项目的一个主要主题是理论和实践之间的协同作用，通过设计和实现在实践中快速并接受严格复杂性分析的算法，使符号代数领域和计算理论都受益。 矩阵计算领域的项目方法将结合现有两种方法的联合收割机要素，即几何和抽象结构（“黑盒”）框架。 该项目还包括群论，组合学和计算机科学的相关问题，通过涉及组概念的对象的算法研究连接。 特别是，这些工具的组合将需要重新研究的瓶颈，阻碍了进展的图同构问题和相关的陪集交叉问题的置换群。 研究员亦会研究布尔函数在对称条件下的参数，包括性质测试的复杂性;以及阿贝尔沙堆模型，它连接了许多领域，包括统计力学，代数图论，离散动力系统，算法以及研究某个交换幺半群和群的复杂性。群是对称性的数学公式，在数学和科学中无处不在。 有限群及其相关凯莱图的算法有着广泛的应用，从群论到统计学、网络设计、图同构问题（与计算机科学和化学文献相关）、密码学以及高对称性对象的构造。 该项目的更广泛的影响主要是通过在GAP中实施新算法，GAP是一个领先的开放访问计算机代数系统，为群论，代数，图论，编码理论和设计理论的研究提供计算环境。 GAP的发展也是对教育的重大贡献，因为在本科抽象代数课程中使用GAP的需求越来越大。