Abstract
Pseudorandom number generators (PRGs) which fool certain statistical tests unconditionally are well studied in complexity, to understand the power of randomness in computation. Such generators have since found many applications in algorithm design, especially in settings like hashing or streaming where the input is large and true randomness is prohibitively costly.
In this talk, we describe a template for PRG construction based on combining a few strings where the level of independence in a string gradually increases. This paradigm has recently led to optimal PRGs for several classes of tests including halfspaces, combinatorial rectangles/shapes, read-once DNFs, and to optimal constructions of hash functions families for load-balancing, min-wise hashing and dimension reduction. Also, the PRGs/hash functions given by this paradigm are typically quite simple: they are variants on the XOR/interleaving of a few strings with limited independence. We speculate about other problems where this paradigm could apply.
(Based on joint work with coauthors, and disjoint work by other researchers).