Proving and Using Pseudorandomness

Workshop | March 6 – 10, 2017 every day |  Calvin Laboratory (Simons Institute for the Theory of Computing)

 Simons Institute for the Theory of Computing

One theme of this workshop will be how to leverage weak pseudorandomness properties, fooling simple classes of tests, in order to derive stronger pseudorandomness properties related to more complex tests. In the setting of additive combinatorics, what is the minimal set of tests that primes have to satisfy in order to guarantee that they contain arithmetic progressions (or other structures)? For example, recent work of Conlon, Fox and Zhao shows that a “correlation condition” initially imposed in the work of Green and Tao is not necessary.

In complexity theory, most unconditional constructions of pseudorandom generators ultimately all rely on various combinations of four basic tools: k-wise independence, small-bias distributions, error-correcting codes, and random walks in expanders. The technical core of the analysis of known pseudorandom generators is to show that pseudorandomness against simple tests implies pseudorandomness against more complex tests (see for example Braverman’s theorem). Explicit constructions of pseudorandom objects have been essential to derandomize algorithms such as primality testing and undirected connectivity, and they have been applied in cryptography, distributed systems, complexity theory, streaming algorithms and learning theory. This workshop will explore unconditional constructions of pseudorandom objects at the frontier of progress, such as pseudorandom generators for small-space computations, small-depth circuits with modular gates, threshold circuits and DNFs.

Organizers:
David Conlon (University of Oxford), Raghu Meka (UCLA; chair), Russell Impagliazzo (UC San Diego), Luca Trevisan (Simons Institute, UC Berkeley).

  Register online

 simonsevents@berkeley.edu, 510-664-9856