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

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

• 批准号: 0405105
• 负责人: Vladimir Shpilrain
• 金额: --
• 依托单位: CUNY City College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0405105&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提出的，现在是非常活跃的研究课题.泛型在"随机“代数对象的代数、几何和算法性质以及它们的自然几何不变量和决策问题的泛型情况行为中表现出许多不同的层次. 正如提出者的工作已经证明的那样，一般的方法通常会导致发现具有真正新的和有趣的属性的对象。例如，一般性提供了一个全新的群论刚性的来源，与半单李群中格提供的标准来源完全不同。以前对无限群概率方面的许多研究主要集中在分析问题上，如顺从性，随机游动的渐近性质，泊松边界，这个项目将集中于理解随机群论对象的代数和算法性质，以及各种传统上研究的群的几何不变量的概率性质。提议者已经取得实质性进展的具体专题将包括：类属群的同构刚性，“随机”货车坎彭图和类属Dehn函数的分析，类属子群畸变和自同构的类属伸缩因子，以及自由群的外自同构群在自由群的“频率空间”上的作用。随着现代计算机的迅速发展，理解各种算法性能的实际行为变得越来越重要。然而，迄今为止，大多数理论研究都涉及算法的最坏情况分析，这通常与算法的实际性能无关。另一方面，在许多实际应用中，特别是在公钥密码学中，有大量关于算法实际性能的实验数据在理论上没有得到充分的解释。目前的项目应该提供一些新的基准思想和理论工具，用于研究和解释群论和计算复杂性的广泛领域中的算法的概率性质和实际行为。