Anti-Concentration, Random Structures, and 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).