CAREER: Pseudorandom Objects and their Applications in Computer Science

自20世纪70年代以来，计算机科学中最成功的范例之一是在计算中使用随机比特(掷硬币)，这可以从几个广泛的方面进行论证。例如，许多简单的随机化算法比复杂的确定性算法性能更好，随机比特在现代密码学中被广泛使用以确保安全性。此外，在设计组合对象(例如高度连接的稀疏网络)的某些应用中，简单地选择一个随机对象通常可以获得最佳参数。然而，随机比特的使用是有代价的：在实践中，高质量的随机比特往往太昂贵，而且许多应用程序，如设计稀疏网络的例子，需要确定性的结构，而不是随机的结构。这个项目的首要目标是理解一个基本问题，即什么时候以及如何用伪随机对象来取代随机位或随机对象的使用，伪随机对象是指被确定地构造但行为像随机对象的对象。这将导致对计算中随机位本质的更深入的理解，以及在理论和实践中对重要问题的更有效和更安全的解决方案。优势的例子包括处理大数据集的更快算法、更强大的网络以及在恶劣环境中更可靠的通信。该项目还包括指导博士生的计划，将研究主题整合到吸引不同背景学生的课程和书籍中，以及支持计算机科学领域中代表性不足的学生群体。该项目包含三套具体目标。第一组目标通常寻求了解如何使用两种称为伪随机生成器和随机性抽取器的伪随机对象来减少计算中的随机比特的数量或质量。伪随机生成器是一个函数，它将一个短的随机种子拉伸成一个在某些函数看来是随机的长字符串，它可以用来减少所需的随机位的数量。随机性抽取器是将不完美的随机源转换成高质量随机比特的功能。第二组目标是研究这些伪随机物体与计算复杂性理论之间的联系。具体地说，目标是利用这些对象的类随机性质来给出确定性对象的新结构，以绕过长期存在的开放问题中的障碍，例如顺序计算与并行计算的问题。第三组目标涉及开发用于构造纠错码的新技术，这种纠错码既可用于防止来自对手的各种篡改攻击，也可用于在密码系统中实现隐私或安全。对这些主题的研究基于几个相关领域的技术，如概率论、信息论、密码学、组合学和调和分析，并将进一步促进这些领域之间的互动以实现突破。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

One of the most successful paradigms in computer science since the 1970s is the use of random bits (coin flips) in computation, which can be demonstrated from several broad aspects. For example, many simple randomized algorithms perform better than sophisticated deterministic algorithms, and random bits are widely used in modern cryptography to ensure security. Moreover, in certain applications regarding designing combinatorial objects (such as highly connected sparse networks), simply choosing a random object often achieves the best parameters. However, the use of random bits comes at a price: in practice high quality random bits are often too costly to obtain, and many applications such as the example of designing a sparse network require deterministic constructions rather than randomized ones. The overarching goal of this project is to understand the fundamental question of when and how one can replace the use of random bits or randomized objects by pseudorandom objects, which are objects that are deterministically constructed but behave like random ones. This will lead to a deeper understanding of the nature of random bits in computation, as well as more efficient and secure solutions to important questions both in theory and in practice. Examples of benefits include faster algorithms for handling large data sets, more robust networks, and more reliable communications in hostile environments. The project also involves plans for mentoring PhD students, integration of the research topics into courses and books that appeal to students from a variety of different backgrounds, and support of under-represented groups of students in computer science.The project contains three sets of specific goals. The first set of goals seeks to understand how to reduce the quantity or quality of random bits in computation generally, using two kinds of pseudorandom objects known as pseudorandom generators and randomness extractors. A pseudorandom generator is a function that stretches a short random seed into a long string that looks random to certain functions, and it can be used to reduce the quantity of random bits required. A randomness extractor is a function that transforms imperfect random sources into high quality random bits. The second set of goals investigates the connections of these pseudorandom objects to computational complexity theory. Specifically, the goal is to use the random-like property of these objects to give new constructions of deterministic objects that circumvent barriers in long-standing open problems, such as the question of sequential computation versus parallel computation. The third set of goals involves development of new techniques for constructions of error-correcting codes, which can be used both to protect against various tampering attacks from adversaries, and to achieve privacy or security in cryptographic systems. The study of these topics is based on techniques from several related areas such as probability theory, information theory, cryptography, combinatorics, and harmonic analysis, and will further foster the interactions among these areas towards breakthroughs.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.