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 还打算帮助提供新的教育机会，特别是在学习数学问题解决技能方面，这是数学和计算机科学研究的关键组成部分。