AF: Small: New Approaches to Complexity Theory Lower Bounds

复杂性理论旨在理解哪些计算任务可以有效地解决，哪些不能。这一理论对于大多数计算机系统的开发至关重要，这些系统需要在有限的时间或内存内处理大量数据。它也是大多数现代密码学和电子商务的基础。复杂性理论的一个基本目标是证明重要计算任务的“下限”，也就是说，证明这些任务不能有效地解决。这项研究的目标是开发新的方法来下限，并使用它们来取得进展的长期开放的问题。该项目是广泛的：它跨越了复杂性的几个子领域，并将促进数学和计算机科学之间的交叉施肥。其教育计划包括开发新课程，附带公开材料，包括讲座笔记和视频，以及研究生和本科生的培训。更详细地说，该项目侧重于四个相互丰富的调查路线。第一个建立在一个连接，最近建立的调查，一组之间的abstractures在傅立叶分析和下限计算函数通过多项式。这里的一个目标是使用这种联系证明新的下界，或者反驳这些假设。第二行是关于采样任务、数据结构和电路的下限，它们也通过研究者建立的连接联系起来。第三个是关于通过低秩矩阵计算函数的下界。最后，第四个奖项是关于通过低通信协议计算组产品的下限。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.