AF: Small: Pseudorandomness for Space-Bounded Computation and Cryptography

Harvard University, Cambridge MA

Investigators

Abstract

Pseudorandomness is the theory of generating objects that "look random" despite being constructed using little or no randomness. Work on pseudorandomness has implications for many different areas of research in computer science, communications, and mathematics. This project seeks to advance the theory and application of pseudorandomness, focusing on two core directions: 1. Pseudorandomness for space-bounded computation and related models: using a new method from the PI's recent work, the project aims to make significant progress on the long-standing "RL vs. L" problem --- whether every randomized algorithm can be made deterministic with only a small increase in memory usage. 2. Pseudorandomness for cryptography: The project will export powerful techniques and concepts from the theory of pseudorandomness to cryptography, in particular exploiting computational measures of randomness that were introduced in the PI's recent work. The research will be closely integrated with the PI's educational efforts. In particular, the PI will continue to develop new curricular, educational, and expository material that are made openly available for others to use. Graduate and undergraduate students will be involved in all phases of this research, and will be given opportunities to publish and present their results at premier international conferences. The PI will also continue his extensive service to the scientific community, including chairing the SIGACT Committee for the Advancement of Theoretical Computer Science. This committee does a substantial amount of outreach activity, interfacing with funding agencies and helping convey the achievements and potentials of research in theoretical computer science to a broad audience.