Efficient Computation in Finite Groups

有限群中的高效计算

• 批准号: 9731799
• 负责人: Akos Seress
• 金额: --
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-01 至 2002-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9731799&HistoricalAwards=false
• 关键词: Efficient; Computation; 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.

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