CAREER: Structure and Analysis of Low Degree Polynomials

职业：低次多项式的结构和分析

• 批准号: 1553288
• 负责人: Daniel Kane
• 金额: $ 50万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1553288&HistoricalAwards=false
• 关键词: CAREER; Structure; Analysis; Low; Degree

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.

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