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.