### DIMACS Theoretical Computer Science Seminar

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$.