AF:Small:Pseudorandomness, Codes, and Distributed Computing

点击翻译按钮获取中文摘要

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.