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.