CAREER: The Polynomial Method in Complexity and Cryptography

计算机科学中的“多项式方法”是指研究布尔函数的代数结构，以低次多项式近似或精确计算的形式。在过去的50年里，它在计算机科学领域取得了许多著名的成果，包括机器学习、量子计算和电路下限等领域。举个例子，量子计算机有可能比今天的经典计算机更有效（对于某些问题），多项式方法已被证明是理解其能力的最有前途的工具之一。这是因为任何可以被量子计算机有效计算的函数都必须在精确意义上被低次多项式很好地近似。该项目旨在提高我们对多项式方法已知公式的理解，并开发新的公式来解决上述应用领域中的主要开放问题。该项目的目标分为两类。第一类集中在多项式方法的一个基本公式，称为近似度，它有许多应用。该项目将开发一种相对较新的技术来证明近似度下界，称为对偶多项式方法，该方法有望解决许多基本函数的近似度。通过已建立的联系，这将影响量子算法领域（它可能意味着各种量子算法的最优性），电路复杂性（它将在基本复杂性度量下解决浅电路的复杂性）和学习理论（它将表征重要对象的能力，包括半空间学习器，噪声容忍学习器和深度网络）。该项目还将研究新的多项式为基础的结构概念，解决这些领域的其他主要开放问题的潜力。第二类目标侧重于多项式方法的不同应用，可验证计算（VC）。VC指的是加密协议，使不可信的证明者能够向验证者保证证明者正确地执行了计算。高效的VC系统将使各种各样的应用成为可能。例如，将数据处理卸载到云的实体可以获得云正确运行的保证。使用多项式方法的理论结果表明，VC协议可以比静态证明更有效，并且在过去的十年中，在构建VC系统方面取得了重大进展，接近实用性，甚至是此类系统的商业部署。尽管如此，许多现有的VC系统具有高成本或缺乏几个关键特性，限制了它们的适用性。该项目将探索多项式方法的新公式，以克服这些局限性。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

The "polynomial method" in computer science refers to the study of the algebraic structure of Boolean functions, in the form of approximation or exact computation by low-degree polynomials. It has led to many celebrated results in computer science over the last 50 years, in areas as diverse as machine learning, quantum computing, and circuit lower bounds. As one example, quantum computers have the potential to be vastly more efficient (for some problems) than today's classical computers, and the polynomial method has proven to be one of the most promising tools available for understanding their power. This is because any function that can be efficiently evaluated by a quantum computer must be well-approximated in a precise sense by low-degree polynomials. This project seeks to improve our understanding of known formulations of the polynomial method, and to develop new formulations to solve major open problems in the aforementioned application domains.The objectives of this project are separated into two classes. The first class focuses on a basic formulation of the polynomial method called approximate degree, which has many applications. The project will develop a relatively new technique for proving approximate degree lower bounds, called the method of dual polynomials, that is poised to resolve the approximate degrees of many basic functions. Via established connections, this will impact the fields of quantum algorithms (where it is likely to imply the optimality of a variety of quantum algorithms), circuit complexity (where it will resolve the complexity of shallow circuits under basic complexity measures), and learning theory (where it will characterize the power of important objects including halfspace learners, noise-tolerant learners, and deep nets). The project will also investigate new polynomial-based notions of structure with the potential to solve additional major open problems in these areas.The second class of objectives focuses on a different application of the polynomial method, to verifiable computing (VC). VC refers to cryptographic protocols enabling an untrusted prover to guarantee to a verifier that the prover performed a computation correctly. Efficient VC systems would enable a wide variety of applications. For example, entities that offload data processing to the cloud could obtain guarantees that the cloud is operating correctly. Seminal theoretical results used the polynomial method to show that VC protocols can be dramatically more efficient than static proofs, and the last decade has seen major progress in building VC systems verging on practicality, and even commercial deployment of such systems. Still, many existing VC systems have high costs or lack several key properties, limiting their applicability. The project will explore new formulations of the polynomial method to overcome these limitations.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.