Award Abstract # 1845349

ABSTRACT

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.

Please report errors in award information by writing to: awardsearch@nsf.gov.