AF: Small: Randomness in Computation - Old Problems and New Directions

AF：小：计算中的随机性 - 老问题和新方向

• 批准号: 1617713
• 负责人: Xin Li
• 金额: $ 37.48万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617713&HistoricalAwards=false
• 关键词: AF; Small; Randomness; Computation; Old

A major goal of computer science is to study how to compute more efficiently using limited resources. The understanding of this question has had profound influence on our daily life, in a variety of areas ranging from e-commerce, cloud computing, to travel planning and weather forecast. In this project the PI seeks to understand how to efficiently use the valuable resource of randomness (such as coin flips) in computation.Randomness is extremely useful in computation and widely used in practice. Simulation of complex models such as those used for weather forecast and economy prediction relies on the use of random processes, and modern computer security will be lost completely without randomness. In this context, the project studies the fundamental questions of the power and limitations of randomness in computation. From a theoretical aspect, it can lead to breakthroughs towards solving long standing open questions in computer science, such as whether randomness is really necessary for algorithms. From a practical aspect, it can lead to improvements in several areas important to society, such as designing streaming and scalable computation protocols for massive datasets, enhancing computer security in an adversarial environment, and tolerating errors in communication protocols. Based on the research activities, the educational component in this project plans to train several Ph.D. students, publish online surveys for free access, integrate research outcomes into courses the PI is or will be teaching, and provide research opportunities for minority students through a joint effort with Johns Hopkins University.The questions that will be addressed in this project include how to generate high quality randomness for computation, how to use randomness in the presence of information leakage or tampering by an adversary, and how to use randomness to detect and correct errors introduced in communications. Two fundamental objects and tools for studying these questions are pseudorandom generators and randomness extractors. A pseudorandom generator is an algorithm that stretches a small number of random bits into a large number of bits that appear to be perfectly random to a certain class of functions. A randomness extractor is an algorithm that converts low quality random sources into very high quality random bits. The project will explore new ways of constructing these objects, as well as the connections between these objects and other areas in computer science, such as cryptography, error correcting codes, and computational complexity. Through this the PI seeks to establish new connections between different areas, and thus leading to possible new breakthroughs.

计算机科学的一个主要目标是研究如何利用有限的资源更有效地进行计算。对这个问题的理解对我们的日常生活产生了深远的影响，涉及电子商务、云计算、旅行计划和天气预报等各个领域。在这个项目中，PI 试图了解如何在计算中有效地利用随机性的宝贵资源（例如抛硬币）。随机性在计算中非常有用，并在实践中广泛使用。天气预报和经济预测等复杂模型的模拟依赖于随机过程的使用，如果没有随机性，现代计算机的安全性将完全丧失。在此背景下，该项目研究了计算中随机性的力量和局限性的基本问题。从理论上讲，它可以为解决计算机科学中长期存在的悬而未决的问题带来突破，例如算法是否真的需要随机性。从实践的角度来看，它可以带来对社会重要的几个领域的改进，例如为海量数据集设计流式和可扩展的计算协议，增强对抗环境中的计算机安全性，以及容忍通信协议中的错误。根据研究活动，该项目的教育部分计划培养数名博士。学生，发布在线调查以供免费访问，将研究成果整合到 PI 正在或将要教授的课程中，并通过与约翰·霍普金斯大学的共同努力为少数族裔学生提供研究机会。该项目将解决的问题包括如何生成高质量的计算随机性，如何在信息泄漏或被对手篡改的情况下使用随机性，以及如何使用随机性来检测和纠正通信中引入的错误。研究这些问题的两个基本对象和工具是伪随机生成器和随机性提取器。伪随机生成器是一种将少量随机位拉伸为大量位的算法，这些位对于某类函数来说似乎是完全随机的。随机性提取器是一种将低质量随机源转换为非常高质量随机位的算法。该项目将探索构建这些对象的新方法，以及这些对象与计算机科学其他领域（例如密码学、纠错码和计算复杂性）之间的联系。通过这种方式，PI寻求在不同领域之间建立新的联系，从而带来可能的新突破。

项目成果

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

编辑距离和最长公共子序列的流式和小空间近似算法

• DOI: 10.4230/lipics.icalp.2021.54
• 发表时间: 2021-07
• 期刊: Leibniz international proceedings in informatics
• 作者: Cheng, Kuan;Farhadi, Alireza;Hajiaghayi, MohammadTaghi;Jin, Zhengzhong;Li, Xin;Rubinstein, Aviad;Seddighin, Saeed;Zheng, Yu
• 通讯作者: Zheng, Yu