权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Research in Complexity Theory

AF：小：复杂性理论研究

基本信息

批准号：
1813930
负责人：
Emanuele Viola
金额：
$ 49.99万
依托单位：
Northeastern University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-06-01 至 2021-12-31
项目状态：
已结题

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

项目摘要

Computational inefficiency is a common experience: the computer cannot complete a certain task due to lack of resources such as time, memory, or bandwidth. The theory of computational complexity classifies -- or aims to classify -- computational tasks according to their inherent inefficiency. Inefficiency can also be harnessed to our advantage. Indeed, modern cryptography and electronic commerce rely on the (presumed) inefficiency of certain computational tasks. From the study of computational complexity there have arisen questions that stand as grand challenges of contemporary science. The objective of this project is to enrich the theory of computational complexity with new directions and techniques, and to use these techniques to make progress on long-standing open problems. Specific areas of investigation include the complexity of sampling tasks and of distributed tasks, and randomness. The investigator has a track record of fruitful exchanges with the mathematics community and will foster further cross-fertilization between mathematics and computer science. The project will develop publicly-available educational material, including lecture notes, surveys, slides, and videos, both at the advanced and at the introductory level. In more detail, the project will seek to prove computational lower bounds for sampling tasks. These lower bounds provide an under-explored angle for attacking problems on extractors and data structures. Preliminary results by the investigator have already found application in a breakthrough known as two-source extractors. The project will also bring a new set of techniques in group theory to bear on communication complexity and cryptography. This project will strengthen these techniques and develop more applications. Finally, the project will explore extensions of small bias generators, which have the potential to answer central open questions in pseudo-randomness and beyond.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的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。