Proving and Using Pseudorandomness

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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 such as the following. 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? 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)? 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. A 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. The 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 formulas in disjunctive normal form. The workshop will bring together complexity theorists, combinatorial mathematicians, number theorists, probabilists and algorithm designers interested in the foundations and uses of pseudo-randomness. It will be open to all potential participants, and the workshop findings (including videorecordings of presentations) will be distributed to the public for comment and engagement. The organizers will encourage students to attend the workshop, and will actively recruit scientists from a diversity of backgrounds to contribute to a wide range of applications.