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

协作研究：群的泛性、几何不变量和算法

• 批准号: 0404991
• 负责人: Paul Schupp
• 金额: --
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0404991&HistoricalAwards=false
• 关键词: Collaborative; Research; Generic; Properties; Groups

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.

几何群论中的泛型思想是由 Gromov 和 Ol'shanskii 提出的，现在是非常活跃的研究主题。泛型在“随机”代数对象的代数、几何和算法特性以及它们的自然几何不变量和决策问题的泛型行为中表现在许多不同的层面上。 正如提议者的工作已经证明的那样，通用方法通常会导致发现具有真正新的和有趣的属性的对象。例如，泛性提供了群论刚性的全新来源，与半简单李群中的格提供的标准来源完全不同。先前对无限群的概率方面的研究大多集中在分析问题上，例如顺应性、随机游走的渐近性质、泊松边界等。该项目将重点了解随机群论对象的代数和算法特性以及各种传统研究的群几何不变量的概率特性。提案者已经取得实质性进展的具体主题将包括：泛群的同构刚性、“随机”van Kampen 图和泛德恩函数的分析、自同构的泛子群畸变和泛拉伸因子，以及自由群的外自同构群在自由群的“频率空间”上的作用。 对于计算机来说，了解各种算法性能的实际行为变得越来越重要。然而，迄今为止，大多数理论研究都涉及算法的最坏情况分析，这通常与其实际性能关系不大。另一方面，在许多实际应用中，特别是公钥密码学，存在大量关于算法实际性能的实验数据，但这些数据尚未在理论上得到充分解释。当前的项目应该提供许多新的基准思想和理论工具，用于研究和解释群论和计算复杂性广泛领域中算法的概率属性和实际行为。