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

伪随机性是一种生成对象的理论，尽管构造时使用的随机性很小或根本没有随机性，但生成的对象看起来是随机的。伪随机性的研究涉及计算机科学、通信和数学的许多不同领域。本项目致力于推进伪随机性的理论和应用，集中在两个核心方向：1.空间有限计算和相关模型的伪随机性：使用PI最近工作的一种新方法，该项目的目的是在长期存在的“RL诉L”问题上取得重大进展--是否每个随机化算法都可以在只增加少量内存的情况下成为确定性算法。伪随机性用于密码学：该项目将从伪随机性理论向密码学输出强大的技术和概念，特别是利用PI最近工作中引入的随机性计算方法。研究将与PI的教育努力紧密结合。特别是，国际和平协会将继续开发新的课程、教育和说明性材料，公开提供给其他人使用。研究生和本科生将参与这项研究的所有阶段，并将有机会在主要的国际会议上发表和展示他们的成果。PI还将继续为科学界提供广泛的服务，包括担任SIGACT理论计算机科学促进委员会的主席。该委员会开展了大量的外展活动，与资助机构建立了联系，并帮助向广大受众传达理论计算机科学研究的成就和潜力。

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.