Department of Computer Science Colloquium
Tuesday April 2nd, 2002 at 4:15pm
Upson Hall B17
Derandomization:
Constructions and Applications
Chris
Umans
http://www.research.microsoft.com/users/umans/
Microsoft Research
Randomness
is pervasive in modern algorithm design, cryptography, and large-scale
simulation in the natural sciences. Reconciling the design of randomized
procedures with their implementation on inherently deterministic machines is of
fundamental importance, as we increasingly rely on the integrity of the
implementations for safety, security, privacy, and the accuracy of computational
science. Derandomization theory addresses this issue.
In
this talk I'll describe two objects designed to provide a sound basis for
implementing randomized procedures: extractors and pseudo-random generators.
I'll present new, simple algebraic constructions of these objects. The
pseudo-random generator construction is the first to produce an optimal tradeoff
between computational hardness and pseudo-randomness, and the extractor
construction significantly simplifies many previous papers while matching the
parameters of the best-known constructions.
I'll
also highlight one of the many applications of extractors outside of
derandomization, answering an important question in logic synthesis regarding
the approximability of DNF formula minimization. Finally, I'll discuss some
other potential applications and various open questions.
(portions
of this talk are joint work with Ronen Shaltiel)