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.