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

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

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.