Workshop on Pseudo-randomness in Mathematical Structures
June 14 - 18, 2010
Organizers: Jean Bourgain, Russell Impagliazzo, Peter Sarnak and Avi Wigderson
Program: http://www.ias.edu/math/pseudo2010/program
Video: https://www.ias.edu/video/pseudo2010
Photos: Photos of the Workshop, by C. J. Mozzochi
A common theme in many seemingly disjoint mathematical areas is to quantify the extent to which natural deterministic mathematical objects have properties similar to those of random objects. For example, is the variance of the distribution of primes approximately that expected for a random set of the same density? When are multiplication and addition over fields ``uncorrelated''? When do the Cayley graphs for groups have the expansion of random graphs? How random are the orbits of natural dynamical systems?
On the other side, computer science applications often require deterministic mathematical structures with such pseudo-random properties. For example, graphs with random-like expansion are used for applications ranging from distributed protocols for leader selection to network routing to sorting. In fact, the central question of computational complexity can be viewed as deterministically constructing a function that is random-like with respect to the ability of small circuits to compute it.
This workshop aimed to highlight parallels and connections between approaches to pseudo-randomness in different areas of mathematics, and between the mathematical and computational approaches to pseudo-randomness. Invited speakers were eminent researchers in such areas as additive number theory, algorithm design, analysis, combinatorics, computational complexity, cryptography, dynamical systems, ergodic theory, group theory, number theory, and statistical mechanics. The first two days of the workshop were devoted to tutorials giving an overview of the role of pseudo-randomness in some of the areas mentioned. These tutorials did not require knowledge of any particular disciplines, and will be accessible to graduate students in all areas of mathematics and computer science. The subsequent three days highlighted exciting related research developments, but was also be accessible to a mixed audience of computer scientists and mathematicians. A list of confirmed speakers and a schedule may be found at http://www.ias.edu/math/pseudo2010/program.
The workshop took place at the Institute from June 14-18, 2010 in Wolfensohn Hall.
The workshop was funded by the National Science Foundation grant DMS-0835373, "Pseudorandomness in mathematics and computer science" and NSF grant CCF-0832797, "Expeditions in Computing." The Workshop was co-sponsored by the Center for Computational Intractability at Princeton University.