Randomness Vs. Memory: A Treasure(s) Hunt

Randomness plays a major role in computation, allowing the execution of tasks that would otherwise be impossible or prohibitively inefficient. Yet the relative power of randomness compared with other resources of computation is mostly unresolved. In this talk we will address the tradeoff between memory and randomness. Namely, can randomness significantly reduce the amount of memory needed for algorithmic tasks? This is one of the central problems in Computational Complexity and its study is tied with the study of pseudorandom generators that fool memory-bounded algorithms (i.e. combinatorial objects that look random to small-memory distinguishers).

There are many exciting questions on the path towards resolving the randomness vs memory problem.  In this talk we will focus on two such areas of research. First, we will discuss small memory algorithms for graph connectivity as well as pseudorandom walks, which we will relate to the general problem of randomness vs. memory. Then we will describe pseudorandom families of hash functions for data structures that are simultaneously small and efficient (with applications to load balancing, the two-choice paradigm, cuckoo hashing, and min-hashing). We will relate such families to progress on more traditional pseudorandom objects such as epsilon-bias sequences and functions with limited independence. 

Omer Reingold is a Professor of Computer Science at the Weizmann Institute of Science and a Visiting Professor at Stanford University. Past positions include Microsoft Research, the Institute for Advanced Study in Princeton, NJ, and AT&T Labs. His research is in the Foundations of Computer Science and most notably in Computational Complexity and the Foundations of Cryptography with emphasis on randomness, derandomization and explicit combinatorial constructions. He is an ACM Fellow and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.