CRII: AF: The Polynomial Method in Learning, Communication, and Quantum Computation

现代计算为处理和分析大型数据集提供了令人兴奋的范例。机器学习、数据流分析和量子计算已经彻底改变了从电子商务到生物信息学再到安全密码系统开发的各个领域。该项目采取统一的方法来理解这些计算范例中的每一个的能力和基本限制。在这些模型中的每一个中可以有效地执行的任务对应于数学上简单的对象，即，可以由低次多项式近似表示的函数。本项目的目标是了解哪些功能具有这些简单的表示，并确定在上述每个领域中这种理解的具体新含义。所有级别的学生将在开展这项研究中发挥重要作用，并将在计算机科学的基础范围内从事广泛的研究领域。第一部分将磨练技术的主体，以理解函数如何被低次多项式近似的两个度量：近似度和阈值度。这些概念已经足以说明多项式近似在许多计算领域中是如何出现的。这项研究将加强和提高的通用性的“对偶多项式的方法”，证明这些量的下界的方法，是基于线性规划对偶。第二部分将为将这些技术应用于更一般的对象奠定基础，包括多项式表示的集合和分布。这些更一般的对象更准确地捕捉机器学习和量子计算中的强大模型，缺乏证明下限的技术，但似乎有必要解决长期存在的开放问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern computing offers exciting paradigms for processing and analyzing large datasets. Machine learning, data-stream analytics, and quantum computing have revolutionized areas ranging from electronic commerce, to bioinformatics, to the development of secure cryptosystems. This project takes a unified approach toward understanding both the power and the fundamental limitations of each of these computing paradigms. Tasks which can be performed efficiently in each of these models correspond to mathematically simple objects, namely, functions which can be approximately represented by low-degree polynomials. The goals of this project are to understand which functions have these simple representations and to identify specific new implications of this understanding within each of the aforementioned areas. Students of all levels will play an essential role in carrying out this research and will be engaged in a broad cross-section of research areas within the foundations of computer science.There are two main technical components of this research project. The first component will hone the body of techniques for understanding two measures of how well functions can be approximated by low-degree polynomials: approximate degree and threshold degree. These notions already suffice to capture how polynomial approximations arise in many areas of computing. This research will strengthen and improve the versatility of the "method of dual polynomials," a method for proving lower bounds on these quantities that is based on linear programming duality. The second component will lay foundations for applying these techniques to more general objects, including sets of and distributions over polynomial representations. These more general objects more accurately capture powerful models in machine learning and quantum computing, against which techniques for proving lower bounds are lacking, but seem necessary to tackle longstanding open questions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.