The idea of genericity in geometric group theory was introduced by Gromov and Ol'shanskii and is now the subject of very active research. Genericity exhibits itself on many different levels in algebraic, geometric and algorithmic properties of ``random'' algebraic objects and in the generic-case behavior of their natural geometric invariants and decision problems. As already demonstrated by the proposers' work, a generic approach often leads to the discovery of objects with genuinely new and interesting properties. For example, genericity provides a totally new source of group-theoretic rigidity, quite different from the standard source provided by lattices in semi-simple Lie groups. Much of the prior research on probabilistic aspects of infinite groups has concentrated on mostly analytic questions, such as amenability, asymptotic properties of random walks, Poisson boundary, and so on. This project will focus on understanding the algebraic and algorithmic properties of random group-theoretic objects as well as probabilistic properties of various traditionally studied geometric invariants of groups. Specific topics, where the proposers have already made substantial inroads, will include: the isomorphism rigidity of generic groups, analysis of ``random'' van Kampen diagrams and generic Dehn functions, generic subgroup distortion and generic stretching factors of automorphisms, and the action of the outer automorphism group of a free group on the ``frequency space'' of a free group.
With the rapid development of modern computers, understanding the practical behavior of the performance of various algorithms is becoming increasingly important. Yet most of theoretical research thus far deals with the worst-case analysis of algorithms, which often has little to do with their practical performance. On the other hand, in many real-life applications, in particular, to public key cryptography, there is a great deal of experimental data on the practical performance of algorithms that has not been adequately explained theoretically. The current project should provide a number of new benchmark ideas and theoretical tools for studying and explaining probabilistic properties and practical behavior of algorithms both in group theory and in the broad field of computational complexity.
