CAREER: A Unified Theory of Pseudorandomness

Harvard University, Cambridge MA

Investigators

Abstract

CAREER: A Unified Theory of Pseudorandomness Salil P. Vadhan During the past few decades, randomization has become one of the most pervasive paradigms in computer science. The best known solutions to many problems in algorithms, cryptography, reliable communication, network design, combinatorics, and distributed computing surprisingly involve making random choices. Thus randomness appears to be very useful, but it is still not known to what extent it is truly necessary. Thus, this research asks: is it possible to reduce or even eliminate the need for randomness in the above settings? The investigators address this question via the paradigm of Pseudorandomness, which is the theory of efficiently generating objects that "look random" despite being constructed using little or no randomness. Specifically, this research builds upon deep connections recently discovered between four pseudorandom objects, namely pseudorandom generators, expander graphs, error-correcting codes, and extractors. The investigators seek to strengthen these connections and use them to attack some of the open problems in the area, such as the construction of expander graphs with optimal expansion, the derandomization of space-bounded computation, and a complete understanding of the relationship between derandomization and circuit lower bounds. Students at all levels are involved in the research, including undergraduates who explore conjectures about expander graphs through computer experiments. The research is tightly integrated into new courses being developed by the investigators, including a graduate course on Pseudorandomness, which focuses on the unified theory that is emerging; and an undergraduate course on Cryptography, which emphasizes the role of pseudorandomness in modern cryptography.