Title: Extractors via constructions of cryptographic pseudo-random generators
Speaker: Marius Zimand, Towson University
Date: April 18, 2006 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Pseudo-random generators are procedures that output strings that are close to random in the complexity-theoretical sense, while extractors are procedures that output strings that are close to random in the information theoretical sense. Since the two notions of randomness are very different, it seems that there can be no transfer of techniques between the methods for building the two primitives. Surprisingly, Trevisan has shown that the Nisan-Wigderson method for building pseudo-rand. generators from hard functions can be used almost directly for building extractors.
In the talk I consider two other well-known methods for constructing pseudo rand. generators, the Blum-Micali-Yao method (using one-way permutations as a building block), and the Hastad-Impagliazzo-Levin-Luby method (using one-way functions as a building block), and show that they yield extractors as well. Even though their parameters are weaker, the new extractors have certain advantages. For example, one extractor is very simple and locally computable (each extracted bit can be computed in polylog time) and one extractor is resilient to an adversary that has bounded access to the weakly random string. This last property is useful for showing a derandomization result for the class of probabilistic sublinear time algorithms: there is a constant natural number $a$ such that for any $T(n) < n^{1/a}$, any algorithm in $BPTIME[T(n)]$ can be simulated deterministically in time $poly(T(n))$ and the simulator is correct except for at most a fraction of $2^{-T(n) \log T(n)}$ of inputs of length $n$.