Collaborative Research: New Algorithms for Group Isomorphism

点击翻译按钮获取中文摘要

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.