Combinatorics, Probability and Computation of Finite Groups

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

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.