AF: Small: Research in 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.