Efficient Computation in Finite Groups

该项目研究有限群的有效操作及其参数的估计。 潜在的应用领域包括计算群论、图同构测试（与化学文档相关）、基于群的高效互连网络，以及可能的基于群的密码学。 主要重点是针对大群理论问题的有效算法的设计和分析。 这些算法将群论的最新成果与新的基本组合结构理论和估计相结合，从中出现了一种全新的算法方法。 一些算法工作在黑盒群的通用性中，因此它们既可以应用于矩阵群，也可以应用于置换群设置。 该项目将从任意表示中细化和扩展经典矩阵群的自然表示的构造。 几个“纯”代数和组合问题也正在研究中。 特别感兴趣的是置换群的基大小问题、有关群在置换域幂集上的作用的问题以及与凯莱图相关的问题：凯莱图的直径以及具有顶点传递自同构群的非凯莱图的研究。 小基数对于快速实现和改进算法的运行时间估计非常重要。 凯莱图直径的估计与膨胀率密切相关，并由此与计算理论和概率论的许多基本问题密切相关。

This project investigates efficient manipulation of finite groups and estimation of their parameters. Potential application areas include computational group theory, graph isomorphism testing (of relevance to chemical documentation), efficient interconnection networks based on groups, and possibly, group-based cryptography. The main focus is on the design and analysis of efficient algorithms for large group theoretic problems. These algorithms combine profound recent results of group theory with new elementary combinatorial structure theory and estimates, from which an entirely new algorithmic methodology emerged. Some of the algorithms work in the generality of black box groups, hence they can be applied both in the matrix group and the permutation group setting. The project will refine and extend the construction of natural representation of classical matrix groups from arbitrary representations. Several "pure" algebraic and combinatorial problems are also being studied. In particular, the interest is in base size problems for permutation groups, problems concerning the action of groups on the power set of the permutation domain, and problems related to Cayley graphs: the diameter of Cayley graphs and the investigation of non-Cayley graphs with vertex-transitive automorphism group. Small bases are important for fast implementations and for improving the running time estimates of algorithms. Estimates of diameters of Cayley graphs are closely related to the expansion rate and through this to a host of basic questions of the theory of computing and probability theory.