Combinatorics, Probability and Computation of Finite Groups

有限群的组合学、概率和计算

• 批准号: 0100042
• 负责人: Igor Pak
• 金额: $ 10.85万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0100042&HistoricalAwards=false
• 关键词: Combinatorics; Probability; Computation; Finite; Groups

The investigator will study finite groups from Combinatorial, Probabilistic and Computational point of view. The research will proceed in three major directions. First, the problem of generating random group elements is studied. The two major venues: Babai algorithms and the product replacement algorithm - both will be attacked by the investigator. Second problem involves recognition of the finite groups based on the random elements. Finally, third problem deals with property testing of groups is studied, by introducing random subproducts as pseudo random elements in the finite group.Finite groups can be viewed as sets of symmetries of finite objects; they are central in understanding of our universe. Finite groups are often unimaginably large, which represents both theoretical and computational difficulties for working with all its elements. Thus the information about the group is often stored in a small set of elements (generators), so that all other group elements can be obtained from these. Now the difficult problem is reversing this encoding and recovering information about the whole group from the generators. The current proposal aims at developments of the new algorithms and improvement of the existing procedures.

研究者将从组合、概率和计算的角度研究有限群。 研究将在三个主要方向上进行。 首先，研究随机群元素的生成问题。两个主要场地：巴白算法和产品替代算法——两者都会受到调查员的攻击。 第二个问题涉及基于随机元素的有限群的识别。最后，通过引入随机子积作为有限群中的伪随机元素，研究了群的性质检验问题。有限群可以看作是有限对象的对称性集；它们是理解我们宇宙的核心。 有限群通常大得难以想象，这代表了处理其所有元素的理论和计算困难。 因此，有关组的信息通常存储在一小部分元素（生成器）中，以便可以从中获取所有其他组元素。 现在的难题是反转这种编码并从生成器中恢复有关整个组的信息。 当前的提案旨在开发新算法和改进现有程序。