CAREER: The Polynomial Method in Complexity and Cryptography

点击翻译按钮获取中文摘要

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.