CAREER: Extractors, Pseudorandom Generators, and Other Explicit Constructions

人们普遍认为物质世界是不可预测的。在计算机科学中，这种不可预测性被建模为随机访问，在算法设计、密码学和分布式计算中被证明是一个有利的特征。例如，已知的在互联网上传输敏感信息的加密方法，在很大程度上依赖于计算机生成随机序列的能力，而许多快速算法都是随机算法。因此，我们有必要研究在有随机性和没有随机性的情况下可以做些什么，并确定在随机性的最小假设下，我们仍然可以从随机方法中获益。这是非随机化领域的核心问题：在计算中不使用随机性，我们能做到什么程度？在这个项目中，PI将研究与非随机化主题相关的基本问题，目的是证明(1)每个随机多项式时间算法都可以用确定性算法模拟，(2)每个小内存的随机算法都可以用小内存的确定性算法模拟，(3)即使有缺陷的随机性来源也可以实现密码学。除了参与围绕提案主题的研究生和本科教学外，PI还将组织阅读小组，参与从代表性不足的群体中招募人才的努力，并参与增加高中教育毕业生招聘的项目。

It is widely acknowledged that the physical universe is unpredictable. In computer science this unpredictability, modeled as access to randomness, turns out to be an enabling feature in algorithm design, cryptography and distributed computing. For example, known methods of encrypting sensitive information for transmission over the internet rely crucially on the ability of computers to generate random sequences, and many fast algorithms are randomized algorithms. So it is worthwhile to investigate exactly what can be done with and without randomness, and to identify the minimal assumptions on the randomness under which we can still get the benefits of randomized methods. This is the central question of the area of derandomization: To what extent can we do without the use of randomness in computation?In this project, PI will investigate basic questions related to the theme of derandomization towards the goals of showing that (1) every randomized polynomial time algorithm can be simulated by a deterministic algorithm, that (2) every randomized algorithm with small memory can be simulated by a deterministic algorithm using small memory, and that (3) cryptography can be achieved even with defective sources of randomness. Besides being involved in graduate and undergraduate teaching around the subject of the proposal, the PI will organize reading groups, participate in efforts to recruit from underrepresented groups, and be involved in projects to increase graduate recruiting at education at the high school level.