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

伪随机生成器是一个有效的过程，它将一个短的输入种子扩展成一个看起来随机的更长的序列。这些迷人的对象有着惊人的各种应用，例如在算法设计、密码学和复杂性理论中。这个项目的主要目标是获得新的伪随机生成器。这一目标将从不同的、相互丰富的途径来实现，其统一的主题是寻求无条件的伪随机生成器，即不依赖于任何未经证实的假设。本文的研究重点是：(1)为重要的计算模型获得新的无条件伪随机生成器；(2)从假设出发分析和提高伪随机生成器的构造效率；(3)发展新的范式和跨学科联系。这项研究与一个项目紧密结合，通过多层次的教育实现广泛的影响。该计划的具体要点是：(1)开发新的理论课程，(2)让各级学生参与，(3)促进跨学科合作。

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.