CAREER: New Pseudorandom Generators: Unconditional Results and Efficient Constructions (TOC)

Northeastern University, Boston MA

Investigators

Abstract

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.