Collaborative Research: Generic Properties of Groups, Geometric Invariants and Algorithms

泛性是由Gromov和Ol‘shanskii在几何群论中引入的，现在是非常活跃的研究主题。泛性表现在许多不同的层次上，表现在“随机”代数对象的代数、几何和算法性质以及它们的自然几何不变和决策问题的一般情况下的行为。正如提出者的工作已经证明的那样，一般的方法通常导致发现具有真正新的和有趣的属性的对象。例如，泛性提供了一个全新的群论刚性来源，与半单李群中的格提供的标准来源有很大的不同，以往关于无限群的概率方面的研究大多集中在分析问题上，如可变性、随机游动的渐近性质、泊松边界等。这个项目将集中于了解随机群论对象的代数和算法性质，以及各种传统研究的群几何不变量的概率性质。这些提出者已经取得重大进展的具体主题将包括：类属群的同构刚性，“随机”范坎本图和类属Dehn函数的分析，自同构的类属子群扭曲和类属伸缩因子，以及自由群的外自同构群在自由群的‘频率空间’上的作用。随着现代计算机的快速发展，理解各种算法的性能的实际行为变得越来越重要。然而，到目前为止，大多数理论研究都是关于算法的最坏情况分析，这往往与它们的实际性能关系不大。另一方面，在许多实际应用中，特别是在公钥密码学中，有大量关于算法实际性能的实验数据，这些数据在理论上没有得到充分的解释。本项目应该为在群论和计算复杂性的广泛领域研究和解释算法的概率性质和实际行为提供一些新的基准思想和理论工具。

The idea of genericity in geometric group theory was introduced byGromov 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 objectsand in the generic-case behavior of their natural geometric invariantsand decision problems. As already demonstrated by the proposers'work, a generic approach often leads to the discovery of objects withgenuinely new and interesting properties. For example, genericityprovides a totally new source of group-theoretic rigidity,quite different from the standard source provided by lattices insemi-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.