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

AF：小：计算机科学中的群论和组合结构

• 批准号: 1423309
• 负责人: Laszlo Babai
• 金额: $ 32.5万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423309&HistoricalAwards=false
• 关键词: AF; Small; Group; theory; combinatorial

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.

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