AF: Medium: Collaborative Research: Exploiting Opportunities in Pseudorandomness

该项目旨在利用新的机会来推进伪随机性理论，这是一种生成“看起来随机”的对象的理论，尽管它们是使用很少或根本没有随机性来构建的。 伪随机性的计算理论起源于20世纪80年代初的密码学基础，此后发展成为理论计算机科学的一个丰富的子领域。伪随机性理论中研究的概念和结构对计算机科学、通信和数学的许多不同研究领域都有影响，包括密码学、计算复杂性、编码理论、加法数论、度量嵌入、流和草图算法以及图论。 该项目高度重视教育、为研究界服务和广泛传播知识。 研究活动将伴随着并与课程开发，研究咨询，服务和推广相结合。 此外，该研究还涉及到安全和隐私等对社会具有重要意义的国家优先事项。具体而言，该项目寻求在几个基本问题上取得进展的新机会，包括：1）RL vs. L问题：试图无条件地证明每个随机算法都可以确定，只有空间效率的常数因子损失; 2）显式构造：寻求显式负载平衡散列函数、批处理代码和深度鲁棒图，其实现实质性参数改进并且对应用具有定性意义，以及3）应用：改进和扩大伪该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准。

This project seeks to exploit new opportunities to advance the theory of pseudo-randomness, which is the theory of generating objects that "look random" despite being constructed using little or no randomness. The computational theory of pseudo-randomness originated in the foundations of cryptography in the early 1980s and has since developed into a rich sub-field of theoretical computer science in its own right. The notions and constructs studied in the theory of pseudo-randomness have implications for many different areas of research in computer science, communications, and mathematics, including cryptography, computational complexity, coding theory, additive number theory, metric embeddings, streaming and sketching algorithms, and graph theory. The project puts high value on education, service to the research community, and wide dissemination of knowledge. The research activities will be accompanied by and integrated with curriculum development, research advising, service, and outreach. In addition, the research also relates to national priorities of importance to society, such as security and privacy.Specifically, the project seeks to exploit new opportunities for progress on several fundamental questions, including: 1) The RL vs. L problem: trying to prove, unconditionally, that every randomized algorithm can be made deterministic with only a constant-factor loss in space efficiency; 2) Explicit constructions: seeking explicit load-balancing hash functions, batch codes, and depth-robust graphs that achieve substantial parameter improvements and have qualitative significance for applications, and 3) Applications: improving and extending the applications of pseudo-randomness to cryptography and data structures.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.