AF:Small:Pseudorandomness, Codes, and Distributed Computing

随机性在计算机科学的许多领域都很有用，包括算法、蒙特卡罗模拟、密码学和分布式计算。然而，在实践中，获得真正的随机数是昂贵的，甚至是不可能的。因此，计算机依赖于伪随机生成器。然而，科学家们报告了实用的伪随机发生器存在的问题。我们能构造出可以证明是好的伪随机生成器吗？PI提出了解决这个问题以及如何从低质量的随机源中提取高质量随机性的相关问题，这些问题与纠错码和分布式计算有着意想不到的联系，PI建议进一步探索这些问题。他还建议解决这些领域的根本问题。在编码理论中，这些问题与他最近关于译码重要的Reed-Muller码的结果有关。在分布式计算方面，他建议推进他在网络提取协议方面的工作。这些协议用于在分布式环境中从低质量的随机源中提取高质量的随机性。这样的协议在密码学中可能非常有用。

Randomness is useful in many areas of computer science, including algorithms, Monte Carlo simulations, cryptography, and distributed computing. In practice, however, it is expensive or impossible to get truly random numbers. Therefore, computers rely on pseudorandom generators. However, scientists have reported problems with practical pseudorandom generators. Can we construct pseudorandom generators that are provably good? The PI proposes to address this question and the related question of how to extract high-quality randomness from low-quality random sources.These questions have unexpected connections to error-correcting codes and distributed computing, which the PI proposes to explore further. He also proposes to attack fundamental questions in these areas. In coding theory, these questions relate to his recent results on decoding the important Reed-Muller codes. In distributed computing, he proposes to advance his work on network extractor protocols. These are protocols to extract high-quality randomness from low-quality random sources in a distributed setting. Such protocols could be very useful in cryptography.