AF:Small:Pseudorandomness and Randomness Extraction

伪随机性和随机性提取的动机是随机性在计算中的惊人效用。在模拟复杂现象(如天气或经济)时，标准做法是包含随机分量。没有随机性，计算机安全是不可能的。然而，在实践中，获得真正的随机数是昂贵的，如果这是可能的话。我们可以用少量的高质量随机性，或者大量的低质量随机性来做什么？伪随机产生器被设计来攻击第一个问题，而随机性抽取器被设计成攻击第二个问题。PI建议加强这些基本对象的建设。这不仅有助于推动计算机科学的发展，而且可以促进使用随机模拟的其他科学领域的进步。此外，这种伪随机对象的构造通常具有意想不到的应用。例如，PI最近展示了如何使用相关的伪随机对象--“扩展图”--来构建无法显著操纵的金融衍生品。一个更常见的应用领域是密码学，这是计算机安全的数学基础。

Pseudorandomness and randomness extraction are motivated by the amazing utility of randomness in computing. When simulating complex phenomena, such as the weather or the economy, it is standard to include random components. Computer security is impossible without randomness. In practice, however, it is expensive to get truly random numbers, if it is possible at all. What can we do with a small amount of high-quality randomness, or a large amount of low-quality randomness? Pseudorandom generators are designed to attack the first question, and randomness extractors the second. The PI proposes to strengthen constructions of these fundamental objects.Not only will this help advance computer science, but it could enable progress in other fields of science which use randomized simulations. Moreover, constructions of such pseudorandom objects often have unexpected applications. For example, the PI recently showed how related pseudorandom objects -- ``expander graphs" -- can be used to construct financial derivatives that cannot be significantly manipulated. A more common application area is cryptography, the mathematical foundation of computer security.