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

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

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.