CAREER: Randomness in Computation

随机性的使用在计算中无处不在，其应用范围包括算法设计、密码学和分布式计算等许多领域。虽然在某些领域，如密码学，没有随机性就做不了什么，但在其他领域，如算法设计，不清楚是否有一个根本原因，即随机性应该是有用的。此外，在随机性至关重要的应用中，通常情况是需要访问纯随机位，但随机性的自然来源通常是有缺陷的。因此，虽然许多应用程序严重依赖于随机技术，但仍有许多与随机性的能力和要求相关的重要问题，以及产生我们仍然不了解的高质量随机性。 该项目的主要研究议程是利用令人兴奋的最新进展来进一步理解这些广泛的方向（这是伪随机性领域的核心问题）。该项目的主要研究目标可以大致分为以下两个方向：（i）无条件去随机化：复杂性理论的一个核心问题是，在高效计算中，随机性是否是必要的。有长期的假设和条件结果表明，人们可以去随机化有效的计算（即，去除随机性的使用，而不付出太多的效率）。该项目的一个中心目标是推动几个重要方向的最新技术，包括使用有限内存的（无条件）去随机化算法，以及迄今为止无法实现的各种电路系列。 研究人员计划通过利用最近出现的多种新方法来解决这些问题，例如利用傅立叶分析结构，以及基于最近概念的去随机化新框架，例如分数伪随机发生器和伪随机伪分布。(ii)从有缺陷的随机性源中提取纯随机比特：作为上述方向的补充，随机性提取领域的重点是从自然界中出现的低质量源中产生纯随机比特。最近在这一领域取得了显著的进展，该项目的重要研究目标包括在有缺陷随机源的现实模型中以及在存在对手的情况下构建更好的提取器，并将其应用于密码学，并调查这种提取器的使用，在无条件的去-该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的知识产权评估的支持。优点和更广泛的影响审查标准。

The use of randomness is ubiquitous in computation, with applications ranging in many areas such as algorithm design, cryptography, and distributed computing. While in some areas, such as cryptography, not much can be done without randomness, in other areas such as algorithm design, it is not clear if there is a fundamental reason that randomness should be useful. Further, in applications where randomness is crucially important, it is often the case that one needs access to purely random bits but natural sources of randomness are typically defective. Thus, while many applications heavily rely on randomized techniques, there are many important questions related to the power and requirement of randomness, as well producing high quality randomness that we still do not understand. The major research agenda of this project is to further our understanding on these broad directions (which are central questions in the area of pseudo-randomness) using exciting recent progress. The project also features activities designed to increase the fraction of undergraduates from disadvantaged backgrounds choosing computer science as a major.The main research goals of this project can be broadly classified into the following two directions: (i) Unconditional de-randomization: A central question in complexity theory is if randomness is necessary in efficient computation. There are longstanding conjectures and conditional results that indicate that one can derandomize efficient computation (i.e., remove the use of randomness without paying much in efficiency). A central goal of this project is to push the state-of-art in several important directions that include (unconditionally) derandomizing algorithms that use limited memory, and various sorts of circuit families that have been beyond reach so far. The investigator plans to tackle these problems by leveraging multiple new approaches that have surfaced recently such as exploiting Fourier analytic structure, and new frameworks of de-randomization based on recent notions such as fractional pseudorandom generators, and pseudorandom pseudo-distributions. (ii) Extracting pure random bits from defective sources of randomness: Complementary to the above direction, the area of randomness extraction focuses on producing purely random bits from low quality sources that occur in nature. There has been remarkable recent progress in this area, and the important research goals of this project include constructing better extractors in realistic models of defective random sources and in the presence of adversaries, with applications to cryptography, and investigating the use of such extractors in unconditional de-randomization pursuits listed above.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.