CAREER: Pseudorandom Objects and their Applications in Computer Science

职业：伪随机对象及其在计算机科学中的应用

• 批准号: 1845349
• 负责人: Xin Li
• 金额: $ 50万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1845349&HistoricalAwards=false
• 关键词: CAREER; Pseudorandom; Objects; their; Applications

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.

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

项目成果

Low-Degree Polynomials Extract from Local Sources

• DOI: 10.48550/arxiv.2205.13725
• 发表时间: 2022-05
• 期刊: ArXiv
• 作者: Omar Alrabiah;Eshan Chattopadhyay;J. Goodman;Xin Li;João L. Ribeiro

Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence

• DOI: 10.4230/lipics.fsttcs.2021.27
• 发表时间: 2021-03
• 期刊: ArXiv
• 作者: Xin Li;Yu Zheng

Improved Decoding of Expander Codes

改进的扩展码解码

• DOI: 10.4230/lipics.itcs.2022.43
• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Chen, Xue;Cheng, Kuan;Li, Xin;Ouyang, Minghui
• 通讯作者: Ouyang, Minghui

Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering

用于交错篡改和篡改组合的不可延展代码、提取器和秘密共享

• DOI: 10.1007/978-3-030-64381-2_21
• 发表时间: 2020
• 期刊: Cham
• 作者: Chattopadhyay, Eshan;Li, Xin
• 通讯作者: Li, Xin

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence

• DOI: 10.4230/lipics.icalp.2021.54
• 发表时间: 2021
• 作者: Kuan Cheng;Alireza Farhadi;M. Hajiaghayi;Zhengzhong Jin;Xin Li;Aviad Rubinstein;Saeed Seddighin;Yu Zheng