Combinatorics, Probability and Computation of Finite Groups

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.