AF: Small: New Approaches to Complexity Theory Lower Bounds

The theory of complexity aims to understand which computational tasks can be solved efficiently, and which cannot. This theory is essential for the development of most computer systems, which need to process large amounts of data within limited time or memory. It is also the basis for most modern cryptography and electronic commerce.

A fundamental objective of the theory of complexity is to prove "lower bounds" for important computational tasks, that is, to show that these tasks cannot be solved efficiently. The goal of this research is to develop new approaches to lower bounds, and to use them to make progress on long-standing open problems. The project is broad: it spans several sub-areas of complexity, and will foster cross-fertilization between mathematics and computer science.

Its education plan includes the development of new courses with accompanying publicly-available material, including lecture notes and videos, as well as training of graduate and undergraduate students.

In more detail, this project focuses on four, mutually-enriching lines of investigation. The first builds on a connection, recently established by the investigator, between a set of conjectures in Fourier analysis and lower bounds for computing functions via polynomials. One goal here is to prove new lower bounds using this connection, or refute the conjectures.

The second line is about lower bounds for sampling tasks, data structures, and circuits, which are also linked via connections established by the investigator. The third is about lower bounds for computing functions via low-rank matrices. Finally, the fourth is about lower bounds for computing group products via low-communication protocols.

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.