CAREER: Structure and Analysis of Low Degree Polynomials

复杂性理论的主要目标是设计快速算法来解决各种计算问题，并了解这种算法何时不存在。为了做到这一点，通常需要一些复杂的数学工具。以这种方式使用的最重要的工具之一是多项式。多项式的变化足以表达或近似一些感兴趣的对象，但也足够简单，它们的性质可以很容易地理解。因此，将问题对象的属性与多项式的属性联系起来是一种众所周知的技术，它出现在计算机科学的许多领域。不幸的是，我们对这些基本物体的理解还远远不够。事实上，我们对许多问题的理解不足，可能会被视为证明我们感兴趣的问题的进一步结果的瓶颈。本项目将着重于弥补这一差距的尝试。特别地，PI计划跟进最近在理解这一领域的几个进展，并试图利用任何新的结果来深入了解计算机科学中的其他重要问题。除了产生具有实际意义的新算法外，该研究还有望对概率论和代数几何等其他领域产生潜在影响。更具体地说，PI打算改进现有的工具来理解许多变量中的低次多项式。特别令人感兴趣的是与随机输入上这种多项式值分布的结果有关的工作，特别关注最近的结构结果，这些结果允许人们将任意多项式分解为表现更好的多项式。取得这些成果后，该项目将继续利用这些改进，以便在理论计算机科学的其他重要问题上取得进展。特别是，在显式伪随机生成器、机器学习和电路复杂性等领域存在许多特定问题，这些技术改进有望提供实质性的新结果。除了这个项目的研究部分，PI还打算帮助提供新的教育机会，特别是关于学习数学解决问题的技能，这是数学和计算机科学研究的关键组成部分。

The primary goal of complexity theory is to design fast algorithms for solving various computational problems and to understand when such algorithms will not exist. In order to do this, a number of sophisticated mathematical tools are often required. One of the more prominent tools used in this way are polynomials. Polynomials are both varied enough to express or approximate a number of objects of interest, and yet are also simple enough that properties of them can be easily understood. Thus, relating properties of the objects in question to properties of polynomials is a well-known technique that shows up in many areas of computer science.Unfortunately, our understanding of these fundamental objects is far from complete. In fact, there are a number of problems for which our lack of understanding can be seen as a bottleneck for proving further results about problems of interest. This project will focus on attempts to remedy this gap. In particular, the PI plans to follow up on several recent advances in understanding of this area and to attempt to leverage any new results to gain insight into other important questions within computer science. In addition to leading to new algorithms of practical import, the research promises to have potential impacts in other fields such as probability theory andalgebraic geometry.More specifically, the PI intends to improve upon existing tools for understanding low degree polynomials in many variables. Of particular interest would be work relating to results on the distribution of the values of such a polynomial on random inputs, with particular focus on recent structural results that allow one to decompose arbitrary polynomials in terms of better behaved ones. Having attained such results, the project will continue by making use of these improvements in order to make progress on other important problems in theoretical computer science. In particular, there are a number of specific problems in the areas of explicit pseudorandom generators, machine learning, and circuit complexity for which such technical improvements show promise for providing substantial new results.In addition to the research component of this project, the PI intends to help provide new educational opportunities particularly with regard to learning mathematical problem solving skills which are a key component of mathematics and computer science research.