CRII: AF: Pseudorandomness in Computer Science

随机性是一个强大的工具，在算法设计、密码学、计算复杂性和分布式计算等计算机科学的各个分支中经常使用。一些解决一些基本问题的最快、最简单、最优雅的算法，如素性测试、多项式因式分解、多项式恒等式测试和图连通性，严重依赖于随机性。这是形成和培育概率计算领域的动力，概率计算领域出现在20世纪70年代的S，作为复杂性理论的一个子领域。经过几十年的研究，有效的随机化算法存在着大量的问题，但对于这些问题，目前还没有有效的确定性算法。复杂性理论中伪随机性理论的一个基本目标是理解有效计算所需的随机性程度。猜想每个多项式时间随机化算法都有一个多项式时间确定性对应物，每个对数空间随机化算法都有一个对数空间确定性对应物。尽管伪随机性领域在最近几年取得了一些突破，但这些基本猜想似乎遥不可及，几个中间的开放问题仍有待解决。为了减少或消除随机性的使用，人们经常面临构造与纯随机对象共享有用性质的显式或弱显式数学对象的问题。例如，为了使所有的对数空间随机化算法去随机化，仅在空间复杂性中具有恒定的系数损失，有效地构造伪随机分布(称为伪随机产生器)就足够了，所述伪随机分布使用较短的随机串来生成对于对数空间算法而言看起来随机的长得多的“伪随机”串。有用的伪随机对象的其他例子是命中集合生成器、采样器、纠错码、扩展器图和随机性抽取器。寻找这些对象的显式构造，具有超越算法去随机化的直接应用。该项目的目标是设计高效的伪随机物体，帮助回答有关随机性在高效计算中的作用的基本问题。该奖项反映了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.