Anti-Concentration, Random Structures, and Sumsets

反集中、随机结构和总和

• 批准号: 1500944
• 负责人: Van Vu
• 金额: $ 30万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1500944&HistoricalAwards=false
• 关键词: Anti; Concentration; Random; Structures; Sumsets

In this project, the goal is to investigate the distribution of random variables arising from practical problems such as solving linear systems of equations or finding the roots of high degree polynomials. These problems are critical in many developments in computer science and engineering. Finding roots of a polynomial is, in particular, a classical and fundamental problem with widespread applications. The main focus of the project is to prove that many natural distributions of random variables do not have large mass on a single point. With this new tool, the investigator hopes to provide answers to long-standing questions such as: In a typical case, how many roots of a polynomial of degree n are real? The principal investigator aims to develop a theory for the anti-concentration phenomenon. Anti-concentration inequalities have been playing an important role in many areas where probability is involved. Recent new insights in the field have led to a significant refinement of several classical results with a broad range of applications. The investigator plans to extend the new results to a more general (nonlinear) setting. Achievements in this direction will have an immediate impact in different fields. Another part of the project continues the study of random discrete structures, in particular, random matrices and random polynomials. The PI will investigate various basic problems, such as properties and distribution of random determinants, the non-existence of multiple eigenvalues and its relation to the QR algorithm, and the classical question: How many roots of a random polynomial are real? He will also investigate sum-set problems in additive combinatorics (for example, an old question of Erdos and Moser on sum-free sets in a group).

在这个项目中，目标是研究由实际问题引起的随机变量的分布，例如解线性方程组或寻找高次多项式的根。这些问题在计算机科学和工程的许多发展中都是至关重要的。特别是多项式的求根问题，是一个有着广泛应用的经典和基本问题。该项目的主要焦点是证明许多随机变量的自然分布在单个点上不具有大质量。通过这一新工具，研究人员希望为长期存在的问题提供答案，例如：在典型情况下，n次多项式的多少个根是实的？首席研究员的目标是发展一种反集中现象的理论。反集中不平等在许多涉及概率的领域发挥着重要作用。最近该领域的新见解导致了几个具有广泛应用范围的经典结果的显著改进。研究人员计划将新的结果推广到更一般的(非线性)环境中。这方面的成就将对不同领域产生立竿见影的影响。该项目的另一部分继续研究随机离散结构，特别是随机矩阵和随机多项式。PI将研究各种基本问题，如随机行列式的性质和分布，多重特征值的不存在及其与QR算法的关系，以及经典问题：随机多项式的多少根是实数？他还将研究可加组合学中的和集问题(例如，Erdos和Moser关于群中和自由集的一个老问题)。