CAREER: Extractors, Pseudorandom Generators, and Other Explicit Constructions

University Of Washington, Seattle WA

Investigators

Abstract

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.