权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Collaborative Research: New Algorithms for Group Isomorphism

协作研究：群同构的新算法

基本信息

批准号：
1750319
负责人：
Joshua Grochow
金额：
$ 10.37万
依托单位：
University of Colorado at Boulder
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-06-01 至 2020-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750319&HistoricalAwards=false
关键词：
Collaborative Research New Algorithms Group

项目摘要

Symmetry reduces large complex systems to manageable quantities of information. Identifying those symmetries and understanding their structure helps to solve a wide range of problems, from improving engineering tasks to disrupting the mechanisms of disease. The century-old problem of deciding whether two sets of symmetries have the same structure is known today as the Group Isomorphism Problem. This problem is fundamental to both computational algebra and computational complexity, and has implications for fields as diverse as material science, particle physics, and chemistry. The primary goal of this project is to develop significantly better approaches to testing isomorphism of finite groups of symmetries. It supports a new multidisciplinary collaboration between researchers at four universities, including students and early-career mathematicians and computer scientists. The Group Isomorphism Problem asks for an algorithm to decide whether two finite groups are equivalent. Both the problem itself, and the techniques designed to improve upon it, have implications for other computational problems, including the better-known problems of Graph Isomorphism and P versus NP. Our team's approach goes beyond existing static recursions such as working sequentially down a derived or lower central series. Using a new dynamic strategy we prioritize the optimal stages of the problem, thereby improving the performance of later stages. To achieve this we are investigating the use of nonassociative rings, spectral sequences, modular representation theory, and p-local cohomology. We are also inspecting recently developed data structures in computational algebra that seem well-suited to our approach, as well as investigating applications to geometric complexity theory.

对称性将大型复杂系统简化为可管理的信息量。识别这些对称性并了解它们的结构有助于解决从改进工程任务到破坏疾病机制的各种问题。决定两组对称是否具有相同结构的百年问题今天被称为群同构问题。这个问题是计算代数和计算复杂性的基础，并对材料科学，粒子物理学和化学等不同领域产生影响。这个项目的主要目标是开发更好的方法来测试有限对称群的同构。它支持四所大学的研究人员之间的新的多学科合作，包括学生和早期职业数学家和计算机科学家。群同构问题要求一个算法来判定两个有限群是否等价。这个问题本身，以及设计来改进它的技术，对其他计算问题都有影响，包括更著名的图同构和P对NP问题。我们团队的方法超越了现有的静态递归，例如顺序地向下工作派生或较低的中心序列。使用一种新的动态策略，我们优先考虑的问题的最佳阶段，从而提高后期阶段的性能。为了实现这一点，我们正在研究使用非结合环，谱序列，模表示理论，和p-局部上同调。我们还检查最近开发的数据结构的计算代数，似乎非常适合我们的方法，以及调查应用几何复杂性理论。