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.