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.
