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.

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