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.
