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

Johns Hopkins University, Baltimore MD

Investigators

Abstract

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.