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.