CRII: AF: Pseudorandomness in Computer Science

Ohio State University, The, Columbus OH

Investigators

Abstract

Randomness is a powerful tool with frequent utility in various branches of computer science such as algorithm design, cryptography, computational complexity, and distributed computing. Some of the fastest, simplest and most elegant algorithms for several fundamental problems, such as primality testing, polynomial factorization, polynomial identity testing, and graph connectivity rely heavily on randomness. This was a motivation for the formation and cultivation of the field of probabilistic computation, which emerged in 1970's as a subfield of complexity theory. After decades of research, there is an abundance of problems with efficient randomized algorithms, for which no efficient deterministic algorithms are known. A fundamental goal in theory of pseudorandomness in complexity theory is to understand the extent to which randomness is necessary for efficient computation. It is conjectured that every polynomial time randomized algorithm has a polynomial time deterministic counterpart, and every log-space randomized algorithm has a log-space deterministic counterpart. Even though the area of pseudorandomness has witnessed several breakthroughs over the recent years, these fundamental conjectures seem far out of reach, and several intermediate open problems remain to be resolved. In order to reduce or remove the use of randomness, one often faces the problem of constructing explicit or weakly explicit mathematical objects that share useful properties with purely random objects. For example, in order to derandomize all log-space randomized algorithms with only a constant factor loss in space complexity, it is sufficient to efficiently construct pseudorandom distributions (called pseudorandom generators) that use a short random string to generate a much longer ``pseudorandom'' string that looks random to log-space algorithms. Other examples of useful pseudorandom objects are hitting set generators, samplers, error correcting codes, expander graphs, and randomness extractors. Finding explicit constructions of these objects, have immediate applications that go beyond derandomization of algorithms. The goal of this project is to design efficient such pseudorandom objects that help answer fundamental questions about the role of randomness in efficient computation. 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.