Summary | Rationale | Images | Credits | Powerpoint Δ | Comments | All Nuggets
What does it mean for a deterministic system to behave randomly?
The fundamental insight of the computational theory of pseudorandomness is to see randomness as dependent on the observer, and that when a specific class of observations is chosen, a deterministic or nearly-deterministic system can be proved to be indistinguishable from a random one. The theory, whose claim to fame is to provide a foundation for modern cryptography, has also led to efficient deterministic simulations of randomized algorithms, and its language and tools can bear both on the construction of graphs (and other objects) with pseudorandom properties, and on proving that specific objects (such as the primes) have pseudorandom properties.
A mutually beneficial interaction between computer scientists and pure mathematicians is ongoing on the problem of constructing pseudorandom graphs and related objects. A similar converge is taking place for problems in additive number theory.
Do the primes "behave like" a random set of integers where the integer n is chosen with probability 1/logn? Is it possible to design a communication network whose topology "behaves like" a random graph? Are there pseudorandom generators that, once initialized with a random seed, give an output that "behaves like" a sequence of random bits? And what do those questions even mean?
The key insight of the computational theory of pseudorandomness is that randomness depends on the observer, and that when a specific class of observations is chosen, a deterministic or nearly-deterministic system can be proved to be indistinguishable from a random one.
Much work in analytic number theory can be seen as partial positive answers the first question for specific statistical properties of the primes. Constructions of expander graphs can be seen as ways of positively answering the second question with respect to connectivity property (and their applications are numerous), and the existence of non-trivial cryptographic systems hinges on the existence of a positive answer to the third question, with respect to all efficient observers.
Recent work in analytic number theory, such as the Green-Tao theorem on arithmetic progressions in the primes, has found ways to prove that seemingly weaker pseudorandomness properties imply seemingly stronger ones; this line of arguments, which, essentially, employs reductions, is typical of the computational theory of pseudorandomness, and the language and tools of complexity theory and cryptography are likely to help further progress. The ideas used to prove unconditional pseudorandomness results in number theory seem in turn helpful to attack problems in computer science. A similar mutually beneficial interplay between computer scientists (and their focus on modular constructions and combinatorics) and pure mathematicians (who bring sharper analytical tools) has been very successful in the construction of expander graphs and other graphs with pseudorandom properties.
written by Luca Trevisan, with contributions from Sanjeev Arora, Valentine Kabanets, and Avi Wigderson.
A sieve of Eratosthenes (such as http://mgccl.com/files/primespiral500.png) and the picture of a small expander, like the one in http://www.ams.org/notices/200407/what-is.pdf.
Let me elaborate my reservation. Pseudo-random generators of Blum-Micali type are robust: presumably the entire Universe lacks resources to distinguish them from true randomness. Confusing this concept with surrogates -- strings which have some similarity to randomness under very (often artificially) restricted testing conditions does a disservice to a really fundamental idea.
