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.
