CRII: AF: Pseudorandomness in Computer Science

随机性是一种强大的工具，在算法设计、密码学、计算复杂性和分布式计算等计算机科学的各个分支中经常使用。一些最快，最简单和最优雅的算法，如素性测试，多项式分解，多项式身份测试和图连通性严重依赖于随机性。这是概率计算领域的形成和发展的动机，该领域在20世纪70年代作为复杂性理论的一个子领域出现。经过几十年的研究，有大量的问题与有效的随机算法，没有有效的确定性算法是已知的。复杂性理论中伪随机性理论的一个基本目标是理解随机性对有效计算的必要程度。证明了每一个多项式时间随机化算法都有一个多项式时间确定性算法，每一个对数空间随机化算法都有一个对数空间确定性算法。尽管近年来伪随机性领域已经取得了一些突破，但这些基本的知识似乎还远未达到，一些中间的开放问题仍有待解决。为了减少或消除随机性的使用，人们经常面临的问题是构造显式或弱显式的数学对象，这些对象与纯随机对象共享有用的属性。例如，为了去随机化所有的对数空间随机化算法，在空间复杂度中只有一个常数因子损失，有效地构造伪随机分布（称为伪随机发生器）就足够了，该伪随机分布使用一个短的随机字符串来生成一个长得多的“伪随机”字符串，该字符串在对数空间算法中看起来是随机的。有用的伪随机对象的其他示例是命中集生成器、采样器、纠错码、扩展图和随机性提取器。找到这些对象的显式构造，有超越算法去随机化的直接应用。该项目的目标是设计有效的伪随机对象，帮助回答有关随机性在有效计算中的作用的基本问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Randomness is a powerful tool with frequent utility in various branches of computer science such as algorithm design, cryptography, computational complexity, and distributed computing. Some of the fastest, simplest and most elegant algorithms for several fundamental problems, such as primality testing, polynomial factorization, polynomial identity testing, and graph connectivity rely heavily on randomness. This was a motivation for the formation and cultivation of the field of probabilistic computation, which emerged in 1970's as a subfield of complexity theory. After decades of research, there is an abundance of problems with efficient randomized algorithms, for which no efficient deterministic algorithms are known. A fundamental goal in theory of pseudorandomness in complexity theory is to understand the extent to which randomness is necessary for efficient computation. It is conjectured that every polynomial time randomized algorithm has a polynomial time deterministic counterpart, and every log-space randomized algorithm has a log-space deterministic counterpart. Even though the area of pseudorandomness has witnessed several breakthroughs over the recent years, these fundamental conjectures seem far out of reach, and several intermediate open problems remain to be resolved. In order to reduce or remove the use of randomness, one often faces the problem of constructing explicit or weakly explicit mathematical objects that share useful properties with purely random objects. For example, in order to derandomize all log-space randomized algorithms with only a constant factor loss in space complexity, it is sufficient to efficiently construct pseudorandom distributions (called pseudorandom generators) that use a short random string to generate a much longer ``pseudorandom'' string that looks random to log-space algorithms. Other examples of useful pseudorandom objects are hitting set generators, samplers, error correcting codes, expander graphs, and randomness extractors. Finding explicit constructions of these objects, have immediate applications that go beyond derandomization of algorithms. The goal of this project is to design efficient such pseudorandom objects that help answer fundamental questions about the role of randomness in efficient computation.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.