Computational Complexity of Group Theoretic Problems and Graph Isomorphism

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

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.