AF: Small: New Approaches to Complexity Theory Lower Bounds

AF：小：复杂性理论下界的新方法

基本信息

批准号：
2114116
负责人：
Emanuele Viola
金额：
$ 50万
依托单位：
Northeastern University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-06-15 至 2025-05-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2114116&HistoricalAwards=false
关键词：
AF Small New Approaches Complexity

项目摘要

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.

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