AF: Small: Group theory and combinatorial structures in computer science

该项目将有助于我们理解计算过程的基本性质。 它将进一步整合数学和理论计算机科学的某些领域，特别是群论和数学中的高度对称组合结构理论，以及图形算法理论和布尔函数理论。该项目的主要目标之一是图同构（GI）问题：确定两个图是否相同。这是数学和科学（如化学）中对象分类的一个基本问题;它也是所谓的“SAT求解器”（SAT solvers）的一个组成部分，这是一种通用的优化方法。GI代表了计算理论中最大的挑战之一，因为它的基本性质和其臭名昭著的未解决的复杂性状态。 这个问题与图的对称性研究密切相关，因此也与有限群的结构和算法问题密切相关。 PI和他的合作者最近已经克服了与这个问题有关的几十年的障碍;在这一势头的基础上，PI希望在这个方向上取得进一步的重大进展，使用群论和组合技术的组合来开发。在这个项目中要追求的攻击线之一是将这些方法推广到所谓的“原始相干配置”，这是强正则图和一般情况之间的中间类。 另一条攻击线将研究某些类型的置换群的结构，称为“块上的巨作用”，这是经典群论方法解决问题的主要障碍。PI将继续指导研究生和本科生在这一研究课题上。

The project will contribute to our understanding of the fundamental nature of the computational process.  It will further integrate certain areas of mathematics and theoretical computer science, specifically group theory and the theory of highly symmetrical combinatorial structures in mathematics, with the theory of algorithms for graphs and the theory of Boolean functions.One of the main targets of the project is the Graph Isomorphism (GI) Problem: to decide whether or not two graphs are the same. This is a fundamental problem in the classification of objects both in mathematics and in science (such as chemistry); it is also an ingredient in so-called "SAT solvers," a generic approach to optimization problems. GI represents one of the great challenges in the theory of computing because of its fundamental nature and of its notorious unresolved complexity status.  The problem is intimately linked to the study of symmetries of graphs, and therefore to structural and algorithmic problems in finite groups.  The PI and his collaborators have recently overcome several decades-old barriers in connection with this problem; building on this momentum, the PI expects further significant progress in this direction, using a combination of group theoretic and combinatorial techniques to be developed. One of the lines of attack to be pursued in this project is a generalization of these methods to so-called "primitive coherent configurations," an intermediate class between strongly regular graphs and the general case.  Another line of attack will study the structure of certain types of permutation groups referred to as "giant action on blocks" that represent the principal barrier to the classical group-theoretic approach to the problem.The PI will continue to mentor both graduate and undergraduate students on this research topics.