AF: Medium: Collaborative Research: Exploiting Opportunities in Pseudorandomness

这个项目寻求利用新的机会来推进伪随机性理论，这是一种理论，即生成尽管使用很少或根本没有随机性的构造的对象，但仍“看起来随机”的理论。伪随机性的计算理论起源于20世纪80年代初的密码学基础，此后发展成为理论计算机科学的一个丰富的子领域。伪随机性理论中研究的概念和构造对计算机科学、通信和数学中的许多不同领域的研究具有影响，包括密码学、计算复杂性、编码理论、加数理论、度量嵌入、流和草图算法以及图论。该项目高度重视教育，为研究界提供服务，并广泛传播知识。研究活动将与课程开发、研究咨询、服务和外展相结合。此外，这项研究还涉及对社会具有重要意义的国家优先事项，如安全和隐私。具体地说，该项目试图在几个基本问题上开拓新的进展机会，包括：1)RL与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.