A pseudorandom generator is an efficient procedure that stretches a short input seed into a much longer sequence that looks random. These fascinating objects have a striking variety of applications, for example in algorithm design, cryptography, and complexity theory.
The main objective of this project is to obtain new pseudorandom generators. This objective will be approached from different, mutually enriching routes, whose unifying theme is the quest for pseudorandom generators that are unconditional, i.e., do not rely on any unproven assumption. The central points of the research are: (1) Obtain new unconditional pseudorandom generators for important computational models, (2) analyze and improve the efficiency of constructions of pseudorandom generators from assumptions, and (3) develop new paradigms and interdisciplinary connections.
This research is closely integrated with a program to achieve broad impact through education on multiple levels. Specific points of this program are: (1) Develop new theory courses, (2) involve students at all levels, and (3) foster interdisciplinary collaboration.
This project advances our theoretical understanding of "pseudorandom generators." A "pseudorandom generator" is an efficient procedure that stretches a short input sequence -- known as "seed" -- into a much longer output sequence that "looks random" to an "observer" (that is, to a computer test that tries to distinguish the output of the generator from random). These fascinating objects challenge our intuition of randomness and have a striking variety of applications, for example in the following two areas: Algorithm design: Ever since researchers in the 1940's have been employing the Monte Carlo method to obtain efficient randomized algorithms, it has been important to produce very long sequences that are ``random enough'' for those algorithms to work correctly. This need has spurred the development of pseudorandom generators, whose use has evolved over time and has led to theoretical breakthroughs, such as a memory-efficient, deterministic algorithm to find an exit from a maze. Cryptography: The theory of pseudorandom generators constitutes the foundation of the rich cryptographic protocols we enjoy every day. For example, when making a purchase online using a card, the card's information may be processed into a sequence that "looks random" to any observer. This guarantees that a malicious observer learns nothing about the card. Currently, there are many candidate general-purpose pseudorandom generators, but whether their output really "looks random" to a general observer depends on unproven assumptions. On the other hand, special-purpose pseudorandom generators only have to "look random" to restricted classes of observers, and sometimes they can be shown to exist unconditionally. --- This project constructs several new pseudorandom generators that are either more efficient or look "more random" than previously available constructions. For general-purpose generators we give several new candidates that are inspired by pseudorandom generators used in practice, but are more efficient than previous theoretical candidates. This work in particular aims to bridge the significant gap between theoretical constructions and deployed constructions. For special-purpose generators we give several new constructions for well-studied classes of observers, such as polynomials. The results from the project are disseminated broadly. They appear in some of the main venues for research in theoretical computer science, and also in various surveys. In addition to researchers in theoretical computer science, the results have also influenced researchers in mathematics and finance. The team working on the project included several students at all levels -- undergraduate, master, and Ph.D. -- as well as a postdoctoral scientist and a visiting professor.
