Computational Complexity of Group Theoretic Problems and Graph Isomorphism

本项目关注代数问题的复杂性，集中于群算法及其应用。一个主要的焦点是快速并行算法的发展，但为此所需的创新似乎也适用于顺序算法。另一个目标是扩展多项式时间库，特别是通过利用组合因子和Sylow子群等构建块的新技术。新方法的一个显著特点是扩大了只有通过群论的最新进展才能获得的结果，特别是有限单群的分类。即使是对于诸如成员资格测试等幼稚问题的新方法的基础程序也是如此。一项补充性研究侧重于确定在顺序或并行设置中可能仍然困难的问题。几乎所有这些研究都对图同构的检验问题有一定的启示。

This project concerns the complexity of algebraic problems, concentrating on algorithms for groups and their applications. A major focus is on the development of fast parallel algorithms, but the innovations that are needed for this also seem applicable to sequential algorithms. Another goal is the expansion of the polynomial-time library, especially via new techniques that utilize building blocks such as composition factors and Sylow subgroups. A distinguishing feature of the new methods is an expanding involvement of results that have become available only through recent advances in group theory, particularly the classification of finite simple groups. This is the case even for procedures that underlie new approaches to naive issues such as membership testing. A complementary study focuses on identifying the problems that are likely to remain hard, in either sequential or parallel settings. Almost all of these studies have implications for the problem of testing graph isomorphism.