From the Inside: Pseudorandomness

by Valentine Kabanets, Simon Fraser University

What does it mean for a fixed object to be “random-like”? Can we efficiently generate such objects deterministically? Can randomized algorithms be efficiently simulated without any truly random coin tosses? What is random about prime numbers? 

These questions have been studied in various branches of computer science and mathematics, from cryptography and complexity theory to graph theory and number theory, using various notions of pseudorandomness and pseudorandom generators. While the notions of pseudorandomness may be different in different contexts (say, in complexity theory vs. analytic number theory), there turn out to be a few surprising similarities in terms of proof ideas and techniques. These connections not only attest to the universal nature of pseudorandomness, but also allow for the unified treatment and transference of ideas across different areas of mathematics and computer science, leading to new exciting results. Exploring the known connections among various notions of pseudorandomness and establishing new ones has been the main focus of the Simons Institute program on Pseudorandomness.

A pseudorandom object can be defined as having some property shared by most random objects. In graph theory, a Ramsey graph is an important example. The Ramsey theorem (from 1928) shows that, for any fixed number k, there is a number n (called the Ramsey number of k) such that every graph on n nodes will contain either a clique (a set of mutually connected nodes) or an independent set (of mutually disconnected nodes) of size k. How big is the Ramsey number of k? In general, the exact answer is unknown (for k > 5). One way to obtain a lower bound on this number is to construct a graph that does not contain any clique or independent set of size k. Such a graph is called a Ramsey graph. One of the early applications of the famous probabilistic method by Paul Erdős was to show (in 1947) that the Ramsey number of k is at least exponential in (k/2), by arguing that a random graph on n nodes is likely not to have any clique or independent set of size about 2 log n. It is still a big open problem to provide an explicit, efficient deterministic construction of Ramsey graphs with such parameters. The best current construction of graphs on n nodes that achieves the Ramsey property for k exponential in (log log n)^c, for some constant c, was given last year by Gil Cohen. Another recent breakthrough (also from last year) in the area of explicit constructions of Ramsey-like objects is a significantly improved construction of two-source randomness extractors (generalizing bipartite Ramsey graphs) due to Eshan Chattopadhyay and David Zuckerman. These exciting new results bring us much closer to understanding Ramsey graphs and related pseudorandom objects (extractors and expanders), as was explored during the first workshop of the Pseudorandomness program.

A pseudorandom generator is an efficient algorithm for converting a short truly random binary string into a much longer binary string so that the resulting induced distribution on the output strings “looks” indistinguishable from truly uniform distribution by any computationally bounded observer. Pseudorandom generators are said to “fool” the class of such observers, and provide a natural way to derandomize (replace true randomness with pseudorandomness in) randomized algorithms from such a class. The second workshop focused mostly on pseudorandom generators and other uses of pseudorandom objects and the proofs of pseudorandomness. Many results in computational pseudorandomness rely on a few basic tools: k-wise independent generators, small-bias generators, error-correcting codes, and random walks on expander graphs. Such basic objects are often combined to get new objects with much stronger pseudorandomness properties. To prove the strong properties of these new objects, one strategy is to first show that a totally random object would work, and then to argue that a similar proof would continue to work for appropriate pseudorandom objects because they “fool” the properties used in the proof. A number of such results were presented at the workshop. In particular, Amnon Ta-Shma showed an almost optimal construction of small-bias generators, relying on some of the ideas of the famous “zig-zag” construction of expanders due to Reingold, Vadhan, and Wigderson. 

A similar idea of “fooling” proofs that work for random objects is known in mathematics as “structure vs. randomness,” which was the subject of the last workshop of the program. In many cases, a mathematical object can be represented as a “structured” part plus some “pseudorandom” part. Such a decomposition allows one to argue about the properties of such objects by showing that the structured part has the required properties and that the pseudorandom part can be essentially ignored. Examples of such decomposition results include Szemeredi’s regularity lemma (in graph theory) and Impagliazzo’s hardcore lemma (in complexity theory). In additive combinatorics, “pseudorandom” is often taken to mean “to be of small Fourier (Gowers) norm.” This notion of pseudorandomness was used by Green and Tao to prove their remarkable result about the existence of arithmetic progressions in prime numbers. One of the important ingredients in their work is the Dense Model Theorem, which allows the transference of certain results about random integers to those about prime numbers. The Dense Model Theorem of Green and Tao turns out to be closely related to the Hardcore Lemma of Impagliazzo, providing yet another example of deep interconnections among different areas of mathematics and theoretical computer science, made possible by the ubiquitous notion of pseudorandomness. 

Related Articles

Related stories

,