CAREER: A Unified Theory of Pseudorandomness

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

CAREER: A Unified Theory of PseudorandomnessSalil P. VadhanDuring the past few decades, randomization has become one of the mostpervasive paradigms in computer science. The best known solutions tomany problems in algorithms, cryptography, reliable communication,network design, combinatorics, and distributed computing surprisinglyinvolve making random choices. Thus randomness appears to be veryuseful, but it is still not known to what extent it is trulynecessary. Thus, this research asks: is it possible to reduce or eveneliminate the need for randomness in the above settings? Theinvestigators address this question via the paradigm ofPseudorandomness, which is the theory of efficiently generatingobjects that "look random" despite being constructed using little orno randomness.Specifically, this research builds upon deep connections recentlydiscovered between four pseudorandom objects, namely pseudorandomgenerators, expander graphs, error-correcting codes, and extractors.The investigators seek to strengthen these connections and use them toattack some of the open problems in the area, such as the constructionof expander graphs with optimal expansion, the derandomization ofspace-bounded computation, and a complete understanding of therelationship between derandomization and circuit lower bounds.Students at all levels are involved in the research, includingundergraduates who explore conjectures about expander graphs throughcomputer experiments. The research is tightly integrated into newcourses being developed by the investigators, including a graduatecourse on Pseudorandomness, which focuses on the unified theory thatis emerging; and an undergraduate course on Cryptography, whichemphasizes the role of pseudorandomness in modern cryptography.