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)