Pseudorandomness

What does it mean for a fixed object to be “random-like”? Is it possible to turn existence proofs that use the probabilistic method into explicit constructions? Is it possible to simulate randomized algorithms deterministically? When can heuristic arguments that treat the primes as a random set of integers be turned into rigorous proofs?
 

Notions of pseudorandomness and quasirandomness have been developed and investigated in several areas of theoretical computer science, combinatorics and number theory (including complexity theory, cryptography, graph theory, additive combinatorics and analytic number theory) to answer such questions. At a very high level, the appeal of such notions is that one can easily prove that certain properties are true for random objects, using probabilistic methods, and then transfer such properties to pseudorandom objects, provided that the pseudorandomness “fools” the probabilistic techniques.
 

These different research communities have developed, independently, different concepts of pseudorandomness, and different technical approaches to proving that specific objects are pseudorandom. In the past, interactions between these communities have led to unified ways of thinking about such definitions and techniques, and new ideas were enabled by such unified views. Recently, there have been a number of breakthroughs in the areas to be covered by this program, for example in the construction of expanders and extractors, or the understanding of pseudorandomness properties of the primes. Other areas are ripe for the next breakthrough, for example the construction of complexity-theoretic pseudorandom generators, or a better quantitative understanding of higher-order non-uniformity over finite fields.
 

The goal of the semester, which will gather researchers in theoretical computer science, combinatorics and number theory, is threefold: to make recent ideas more broadly understood beyond the community in which they originated; to make a concerted effort toward the long-standing open problems in this area; and to explore new questions generated during the program by the interaction between different communities. In addition, concurrently with this program MSRI will be hosting two semester-long programs with a thematic connection, on Analytic Number Theory (http://www.msri.org/programs/297) and Harmonic Analysis (http://www.msri.org/programs/300). We expect there to be fruitful interactions and synergies between all three programs.